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();
    }
}