Lists permutations (unknown number) [duplicate]

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).