Advertisement
Guest User

Untitled

a guest
Jul 23rd, 2017
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.31 KB | None | 0 0
  1. ```C#
  2. using System;
  3. using System.Collections.Generic;
  4. using System.Linq;
  5.  
  6. using static System.Console;
  7.  
  8. namespace pinter_8.A._1_multiplying_permutations
  9. {
  10. class Program
  11. {
  12. static void display(Dictionary<int, int> f)
  13. {
  14. foreach (var key in f.Keys.OrderBy(elt => elt)) Write($"{key} "); WriteLine();
  15. foreach (var key in f.Keys.OrderBy(elt => elt)) Write($"{f[key]} "); WriteLine();
  16. }
  17.  
  18. static void display(List<List<int>> cycles)
  19. {
  20. foreach (var cycle in cycles)
  21. {
  22. Write("(");
  23. foreach (var i in cycle) Write(i);
  24. Write(")");
  25. }
  26.  
  27. WriteLine();
  28. }
  29.  
  30. static Dictionary<int, int> permutation(string s) =>
  31. Enumerable.Range(1, s.Count())
  32. .Zip(
  33. s.Select(elt => elt - '0'),
  34. (k, v) => (key: k, value: v))
  35. .ToDictionary(kv => kv.key, kv => kv.value);
  36.  
  37. static List<int> get_cycle(Dictionary<int,int> f, int i)
  38. {
  39. var result = new List<int>();
  40.  
  41. while(true)
  42. {
  43. if (result.Contains(i)) return result;
  44.  
  45. result.Add(i);
  46.  
  47. i = f[i];
  48. }
  49. }
  50.  
  51. static List<List<int>> permutation_to_disjoint_cycles(Dictionary<int, int> f) =>
  52. Enumerable.Range(1, f.Keys.Max())
  53. .Aggregate(
  54. new List<List<int>>(),
  55. (result, i) =>
  56. result.SelectMany(elt => elt).Contains(i) ? result :
  57. f[i] == i ? result :
  58. result.Concat(new List<List<int>> { get_cycle(f, i) }).ToList());
  59.  
  60. static void display_permutation_as_disjoint_cycles(string s)
  61. {
  62. display(permutation(s)); WriteLine();
  63.  
  64. display(permutation_to_disjoint_cycles(permutation(s)));
  65.  
  66. WriteLine("--------------------");
  67. }
  68.  
  69. static void Main(string[] args)
  70. {
  71. display_permutation_as_disjoint_cycles("492517683");
  72. display_permutation_as_disjoint_cycles("749238165");
  73. display_permutation_as_disjoint_cycles("795312486");
  74. display_permutation_as_disjoint_cycles("987436512");
  75. }
  76. }
  77. }
  78. ```
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement