C# Permutation of an array of arraylists?

I'm surprised nobody posted the LINQ solution.

from val0 in new []{ "1", "5", "3", "9" }from val1 in new []{ "2", "3" }from val2 in new []{ "93" }select String.Format("val0={0};val1={1};val2={2}", val0, val1, val2)

Recursive solution

    static List<string> foo(int a, List<Array> x)    {        List<string> retval= new List<string>();        if (a == x.Count)        {            retval.Add("");            return retval;        }        foreach (Object y in x[a])        {            foreach (string x2 in foo(a + 1, x))            {                retval.Add(y.ToString() + " " + x2.ToString());            }        }        return retval;    }    static void Main(string[] args)    {        List<Array> myList = new List<Array>();        myList.Add(new string[0]);        myList.Add(new string[0]);        myList.Add(new string[0]);        myList[0] = new string[]{ "1", "5", "3", "9" };        myList[1] = new string[] { "2", "3" };        myList[2] = new string[] { "93" };        foreach (string x in foo(0, myList))        {            Console.WriteLine(x);        }        Console.ReadKey();    }

Note that it would be pretty easy to return a list or array instead of a string by changing the return to be a list of lists of strings and changing the retval.add call to work with a list instead of using concatenation.

How it works:

This is a classic recursive algorithm. The base case is foo(myList.Count, myList), which returns a List containing one element, the empty string. The permutation of a list of n string arrays s1, s2, ..., sN is equal to every member of sA1 prefixed to the permutation of n-1 string arrays, s2, ..., sN. The base case is just there to provide something for each element of sN to be concatenated to.

I recently ran across a similar problem in a project of mine and stumbled on this question. I needed a non-recursive solution that could work with lists of arbitrary objects. Here's what I came up with. Basically I'm forming a list of enumerators for each of the sub-lists and incrementing them iteratively.

public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<IEnumerable<T>> lists){    // Check against an empty list.    if (!lists.Any())    {        yield break;    }    // Create a list of iterators into each of the sub-lists.    List<IEnumerator<T>> iterators = new List<IEnumerator<T>>();    foreach (var list in lists)    {        var it = list.GetEnumerator();        // Ensure empty sub-lists are excluded.        if (!it.MoveNext())        {            continue;        }        iterators.Add(it);    }    bool done = false;    while (!done)    {        // Return the current state of all the iterator, this permutation.        yield return from it in iterators select it.Current;        // Move to the next permutation.        bool recurse = false;        var mainIt = iterators.GetEnumerator();        mainIt.MoveNext(); // Move to the first, succeeds; the main list is not empty.        do        {            recurse = false;            var subIt = mainIt.Current;            if (!subIt.MoveNext())            {                subIt.Reset(); // Note the sub-list must be a reset-able IEnumerable!                subIt.MoveNext(); // Move to the first, succeeds; each sub-list is not empty.                if (!mainIt.MoveNext())                {                    done = true;                }                else                {                    recurse = true;                }            }        }        while (recurse);    }}