This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Permutations container

By: digemall on May 1st, 2011  |  syntax: C#  |  size: 3.08 KB  |  views: 88  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. class Program
  2. {
  3.     public class PermutationContainer<T>
  4.     {
  5.         private class Node
  6.         {
  7.             public Dictionary<T, Node> Nodes { get; private set; }
  8.             public T Value { get; private set; }
  9.             public Node(T value)
  10.             {
  11.                 this.Value = value;
  12.                 this.Nodes = new Dictionary<T, Node>();
  13.             }
  14.         }
  15.  
  16.         private Dictionary<T, Node> Roots;
  17.  
  18.         public PermutationContainer()
  19.         {
  20.             Roots = new Dictionary<T, Node>();
  21.         }
  22.  
  23.         /// <summary>
  24.         /// Adds permutation. Returns true if added, false if permutation already exists
  25.         /// </summary>
  26.         /// <param name="perm"></param>
  27.         /// <returns></returns>
  28.         public bool AddPermutation(IEnumerable<T> perm)
  29.         {
  30.             bool added = false;
  31.             Dictionary<T, Node> nodes = Roots;
  32.             foreach (var el in perm)
  33.             {
  34.                 Node currNode;
  35.                 if (!nodes.TryGetValue(el, out currNode))
  36.                 {
  37.                     added = true;
  38.                     currNode = new Node(el);
  39.                     nodes.Add(el, currNode);
  40.                 }
  41.                 nodes = currNode.Nodes;
  42.             }
  43.             return added;
  44.         }
  45.  
  46.         public bool ContainsPermutation(IEnumerable<T> perm)
  47.         {
  48.             Dictionary<T, Node> nodes = Roots;
  49.             foreach (var el in perm)
  50.             {
  51.                 Node currNode;
  52.                 if (!nodes.TryGetValue(el, out currNode))
  53.                 {
  54.                     return false;
  55.                 }
  56.                 nodes = currNode.Nodes;
  57.             }
  58.             return true;
  59.         }
  60.  
  61.         public IEnumerable<IEnumerable<T>> GetPermutations()
  62.         {
  63.             foreach (var node in Roots.Values)
  64.                 foreach (var perm in GetPermutations(node))
  65.                     yield return perm;
  66.         }
  67.  
  68.         private IEnumerable<IEnumerable<T>> GetPermutations(Node n)
  69.         {
  70.             if (n.Nodes.Count == 0)
  71.                 yield return new[] { n.Value };
  72.             else
  73.                 foreach (var node in n.Nodes.Values)
  74.                     foreach (var subPerm in GetPermutations(node))
  75.                         yield return new[] { n.Value }.Concat(subPerm);
  76.         }
  77.     }
  78.  
  79.  
  80.     static void Main(string[] args)
  81.     {
  82.         var perm1 = new[] { "A", "B", "C", "D" };
  83.         var perm2 = new[] { "B", "A", "C", "D" };
  84.         var perm3 = new[] { "D", "B", "A", "C" };
  85.         var perm4 = new[] { "A", "B", "C", "D" };
  86.  
  87.         PermutationContainer<string> pc = new PermutationContainer<string>();
  88.         bool b1 = pc.AddPermutation(perm1);
  89.         bool b2 = pc.AddPermutation(perm2);
  90.         bool b3 = pc.AddPermutation(perm3);
  91.         bool b4 = pc.AddPermutation(perm4); // is false
  92.         bool b5 = pc.ContainsPermutation(perm4); // is true
  93.  
  94.         foreach (var perm in pc.GetPermutations().ToList())
  95.         {
  96.             Console.WriteLine("Perm: {0}", string.Join(",", perm));
  97.         }
  98.         Console.ReadLine();
  99.     }
  100. }
clone this paste RAW Paste Data