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