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.

are there multiple independent lists or are they connected somehow? Are they in a parent/children relationship? Siblings? — Joel Etherton, Oct 10 '12 at 16:32
They're nested. That would only work if I was iterating over them sequentially. — Flynn1179, Oct 10 '12 at 16:34
Think of a list of columns and a list of rows in a spreadsheet as a two-dimensional example, where I'd need to do something with each cell. I need an n-dimensional solution, unfortunately. — Flynn1179, Oct 10 '12 at 16:35
Would be easier to provide an answer with a more specific `Do something with item1 and item 2`.. — Francis P, Oct 10 '12 at 16:37
Like iterate through N-dimensional array? [C#: N For Loops](http://stackoverflow.com/questions/2129341/c-n-for-loops) — Fung, Oct 10 '12 at 16:45
Depending on what you want to do with the values, you could always write a recursive method. — Bob., Oct 10 '12 at 16:45

score 5 · Accepted Answer · answered Oct 10 '12 at 16:50

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

James Curtis · Answer 2 · 2012-10-10T17:43:43.170

1

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

edited Oct 10 '12 at 17:43

answered Oct 10 '12 at 16:45

James Curtis

784
4
15

@Servy - do you have any evidence of / explanation for that statement? – James Curtis Oct 10 '12 at 16:59
I'm looking for the article on the subject. In the meantime, you need to change `if (index == lists.Count)` to use `Count - 1` or you'll just get index out of bounds errors. – Servy Oct 10 '12 at 17:04
[Found it](http://blogs.msdn.com/b/toub/archive/2004/10/29/249858.aspx). Note it's a 3 part series; this is just the first part. – Servy Oct 10 '12 at 17:08
@Servy - The issue mentioned here is one of recursive iteration, not recursive iterator blocks. The code snipped provided by Eric Lippert, while shorter, still utilizes recursive iteration. – James Curtis Oct 10 '12 at 17:53

score 0 · Answer 3 · answered Oct 10 '12 at 16:33

0

for (int i = 0; i < lists.Length; i++) {
    foreach (Item item in lists[i]) {
       ....
    }
}

answered Oct 10 '12 at 16:33

001

13,291
5
35
66

1

That will only cover a 2-D case (which he explicitly calls out). He want a more general solution for any n-diminsional set of lists. – shenles Oct 10 '12 at 16:41

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

3 Answers3