Lists permutations (unknown number)

Question

Possible Duplicate:
Combination of List<List<int>>

I have multiple Lists, could be 2 or 3 up to 10 lists, with multiple values in them. Now what I need to do is to get a combination of all of them.

For example, if I have 3 lists with the following values:

• List 1: 3, 5, 7
• List 2: 3, 5, 6
• List 3: 2, 9

I would get these combinations

• 3,3,2
• 3,3,9
• 3,5,2 Etc..

Now the problem is I cannot do this easily because I do not know how many lists I have, therefore determine how many loops I need.

Answer 1

You could probably make that a lot easier, but this is what I had in mind just now:

List<List<int>> lists = new List<List<int>>();
lists.Add(new List<int>(new int[] { 3, 5, 7 }));
lists.Add(new List<int>(new int[] { 3, 5, 6 }));
lists.Add(new List<int>(new int[] { 2, 9 }));

int listCount = lists.Count;
List<int> indexes = new List<int>();
for (int i = 0; i < listCount; i++)
    indexes.Add(0);

while (true)
{
    // construct values
    int[] values = new int[listCount];
    for (int i = 0; i < listCount; i++)
        values[i] = lists[i][indexes[i]];

    Console.WriteLine(string.Join(" ", values));

    // increment indexes
    int incrementIndex = listCount - 1;
    while (incrementIndex >= 0 && ++indexes[incrementIndex] >= lists[incrementIndex].Count)
    {
        indexes[incrementIndex] = 0;
        incrementIndex--;
    }

    // break condition
    if (incrementIndex < 0)
        break;
}

If I’m not completely wrong, this should be O(Nm) with m being the number of lists and N the number of permutations (product of the lengths of all m lists).

Answer 2

you could make a List<List<yourValueType> mainlist in which you put all your lists. then with a simple

int numberOfIterations = 1;
foreach(var item in mainlist)
{
    numberOfIterations *= item.Count;
}

this would get the amount of iterations you would have to execute in total.

Answer 3

Non-recursive solution, works on any IEnumerables (not just lists) without solidifying them:

public static IEnumerable<IEnumerable<T>> Permutations<T>(
    this IEnumerable<IEnumerable<T>> source)
{
    // Check source non-null, non-empty?

    var enumerables = source.ToArray();
    Stack<IEnumerator<T>> fe = new Stack<IEnumerator<T>>();
    fe.Push(enumerables[0].GetEnumerator());

    while (fe.Count > 0)
    {
        if (fe.Peek().MoveNext())
        {
            if (fe.Count == enumerables.Length)
                yield return new Stack<T>(fe.Select(e => e.Current));
            else
                fe.Push(enumerables[fe.Count].GetEnumerator());
        }
        else
        {
            fe.Pop().Dispose();
        }
    }
}

Answer 4

Not very efficient but very easy to understand approach might be to solve this task recursively. Consider a method which computes permutations for N lists. If you have such a method then you can easily compute permutations for N+1 lists by combining all permutation of N lists with every number in the last list. You should also handle corner case which permutations of 0 lists. Then implementation seems to be straightforward:

IEnumerable<IEnumerable<T>> GetAllPermutations<T>(IEnumerable<IEnumerable<T>> inputLists)
{
    if (!inputLists.Any()) return new [] { Enumerable.Empty<T>() };
    else
    {
        foreach (var perm in GetAllPermutations(inputLists.Skip(1)))
            foreach (var x in inputLists.First())
                yield return new[]{x}.Concat(perm);
    }
}

Answer 5

As an alternative, following rawlings general idea the following should work

public static IEnumerable<IEnumerable<T>> Permutations<T> (this IEnumerable<IEnumerable<T>> underlying)
{
    var enumerators = new Queue<IEnumerator<T>>(underlying.Select(u => u.GetEnumerator())
                                                          .Where(enumerator => enumerator.MoveNext());
    Boolean streaming = enumerators.Any();
    if(streaming)
    {
        IEnumerable<T> result;

        IEnumerator<T> finalEnumerator = enumerators.Dequeue();
        Func<Boolean,Boolean> finalAction = b => b ? b : finalEnumerator.MoveNext();

        Func<Boolean,Boolean> interimAction = 
         enumerators.Reverse()
                    .Select(enumerator => new Func<Boolean,Boolean>(b => b ? b : (enumerator.MoveNext() ? true : enumerator.ResetMove())))
                    .Aggregate((f1,f2) => (b => f1(f2(b)));
        enumerators.Enqueue(finalEnumerator);

        Func<Boolean,Boolean> permutationAction = 
                              interimAction == null ? 
                              finalAction :
                              b => finalAction(interimAction(b));

        while(streaming)
        {
              result = new Queue<T>(enumerators.Select(enumerator => enumerator.Current))
              streaming = permutationAction(true);
              yield return result;
        }
}

private static Boolean ResetMove<T>(this IEnumerator<T> underlying)
{
     underlying.Reset();
     underlying.MoveNext();
     return false;
}