Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Program
- {
- public class PermutationContainer<T>
- {
- private class Node
- {
- public Dictionary<T, Node> Nodes { get; private set; }
- public T Value { get; private set; }
- public Node(T value)
- {
- this.Value = value;
- this.Nodes = new Dictionary<T, Node>();
- }
- }
- private Dictionary<T, Node> Roots;
- public PermutationContainer()
- {
- Roots = new Dictionary<T, Node>();
- }
- /// <summary>
- /// Adds permutation. Returns true if added, false if permutation already exists
- /// </summary>
- /// <param name="perm"></param>
- /// <returns></returns>
- public bool AddPermutation(IEnumerable<T> perm)
- {
- bool added = false;
- Dictionary<T, Node> nodes = Roots;
- foreach (var el in perm)
- {
- Node currNode;
- if (!nodes.TryGetValue(el, out currNode))
- {
- added = true;
- currNode = new Node(el);
- nodes.Add(el, currNode);
- }
- nodes = currNode.Nodes;
- }
- return added;
- }
- public bool ContainsPermutation(IEnumerable<T> perm)
- {
- Dictionary<T, Node> nodes = Roots;
- foreach (var el in perm)
- {
- Node currNode;
- if (!nodes.TryGetValue(el, out currNode))
- {
- return false;
- }
- nodes = currNode.Nodes;
- }
- return true;
- }
- public IEnumerable<IEnumerable<T>> GetPermutations()
- {
- foreach (var node in Roots.Values)
- foreach (var perm in GetPermutations(node))
- yield return perm;
- }
- private IEnumerable<IEnumerable<T>> GetPermutations(Node n)
- {
- if (n.Nodes.Count == 0)
- yield return new[] { n.Value };
- else
- foreach (var node in n.Nodes.Values)
- foreach (var subPerm in GetPermutations(node))
- yield return new[] { n.Value }.Concat(subPerm);
- }
- }
- static void Main(string[] args)
- {
- var perm1 = new[] { "A", "B", "C", "D" };
- var perm2 = new[] { "B", "A", "C", "D" };
- var perm3 = new[] { "D", "B", "A", "C" };
- var perm4 = new[] { "A", "B", "C", "D" };
- PermutationContainer<string> pc = new PermutationContainer<string>();
- bool b1 = pc.AddPermutation(perm1);
- bool b2 = pc.AddPermutation(perm2);
- bool b3 = pc.AddPermutation(perm3);
- bool b4 = pc.AddPermutation(perm4); // is false
- bool b5 = pc.ContainsPermutation(perm4); // is true
- foreach (var perm in pc.GetPermutations().ToList())
- {
- Console.WriteLine("Perm: {0}", string.Join(",", perm));
- }
- Console.ReadLine();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement