How do you iterate over an arbitrary number of lists, including every permutation?

Question

For example, if I had two lists, I'd do:

foreach (Item item1 in lists[0])
  foreach (Item item2 in lists[1])
    // Do something with item1 and item2

Or if I had three, I'd do

foreach (Item item1 in lists[0])
  foreach (Item item2 in lists[1])
    foreach (Item item3 in lists[2])
      // Do something with item1, item2, and item3

but if I don't know at compile time how many lists are in the lists collection, how can I easily iterate over every permutation?

A C# solution is ideal, but a solution in any language that demonstrates a suitable algorithm would be handy.

A good 2-dimensional example would be a list of columns and a list of rows on a spreadsheet, where I need to do processing on each cell. It's an n-dimensional problem, however.

Answer 1

There is a wonderful article on the subject by Eric Lippert.

I highly suggest reading the article, as it describes the process by which you can arrive at the result, but at the end the resulting code is short and sweet:

(Copied verbatim from the link)

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) 
{ 
  IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
  return sequences.Aggregate( 
    emptyProduct, 
    (accumulator, sequence) => 
      from accseq in accumulator 
      from item in sequence 
      select accseq.Concat(new[] {item})); 
}

Answer 2

    public static IEnumerable<T[]> IterateOverLists<T>(this IList<IEnumerable<T>> lists )
    {
        var array = new T[lists.Count];
        return IterateOverLists( lists, array, 0 );
    }
    private static IEnumerable<T[]> IterateOverLists<T>(this IList<IEnumerable<T>> lists, T[] array, int index)
    {
        foreach (var value in lists[index])
        {
            array[index] = value;
            if (index == lists.Count - 1)
            {
                // can make a copy of the array here too...
                yield return array;
            }
            else
            {
                foreach (var item in IterateOverLists(lists, array, index + 1))
                {
                    yield return item;
                }
            }
        }
    }

If one of your lists is empty it will kill the whole thing, but you should be able to work around that...