Generating Permutations for n sets in LINQ

Question

I have an array of IEnumerable (IEnumerable[]) and would like to generate all possible combinations of the elements in these IEnumerables. It is similar to this problem: Generating Permutations using LINQ but I do not know how many IEnumerables I will have beforehand and thus cannot use the described LINQ statement.

To give an example: My array

IEnumerable[] array;

has for example these elements

array[0]={0,1,2};
array[1]={a,b};

Then I would like these to be returned:

{{0,a},{0,b},{1,a},{1,b},{2,a},{2,b}}

But it might also hold:

array[0]={0,1,2};
array[1]={a,b};
array[2]={w,x,y,z};

Then I would need the appropriate permutations. I do not have any information on how many IEnumerables and no information on how many elements each IEnumerable holds.

Thanks in advance for any help,

Lars

What would you expect the output to be when your input is array[0]={0,1,2}; array[1]={a,b}; array[2]={w,x,y,z}? — David V, May 20 '11 at 15:40
As above, I don't know that the expected output really counts as *all* the permutations. Do you have an assumed constraint that each resulting item have only two elements? — Yuck, May 20 '11 at 15:45
possible duplicate of [Generating all Possible Combinations](http://stackoverflow.com/questions/3093622/generating-all-possible-combinations) — Anthony Pegram, May 21 '11 at 04:10
Also reference: http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx — Anthony Pegram, May 21 '11 at 04:11
@David V: My expected output would then be {{0,a,w},{0,a,x},{0,a,y},{0,a,z},{0,b,w},{0,b,x},{0,b,y},{0,b,z},{1,a,w}...} @Anthony Pegram: The article from Eric Lippert is what I was searching for, very nice and clean. I just have one more problem with this. Since I stated that I need the code to work with an array of untyped IEnumerables (IEnumerable[]) I am struggling to get Erics code to work. With typed IEnumerables it is perfect. — larsbeck, May 23 '11 at 16:35

score 0 · Answer 1 · answered May 20 '11 at 15:57

Try this as a direction (you'll need to modify, I'm sure, and I haven't compiled it, so there may be some syntax errors)

public IEnumerable<string> CompileCominations
    (IEnumberable<string[]> arrays, List<string> combinations)
{
    if(combinations == null) combinations = new List<string>();
    for(int i = arrays.Count() - 1; i >= 0; i--)
    {
       if(combinations.Count >= 1) combinations = 
           Combine2Lists(combinations, arrays[i]);
       else 
       {
           combinations = Combine2Lists(arrays[i], arrays[i -1];
           i--;
       }
    }
    return combinations;
}

private List<string> Combine2Lists
    (IEnumberable<string> list1, IEnumerable<string> list2)
{
    List<string> currentList = new List<string>();
    for(int i = 0; i < list1.Count(); i ++)
    {
        for(int j = 0; j < list2.Count(); j++)
        {
            currentList.Add(
              string.Format("{0},{1}", list1[i], list2[j]);
        }
    }
    return currentList;
}

Again, not compiled, but what it should do is keep adding "item1, item2" to a list with a where item1 = the old "item1, item2" and item2 = just the new entry from the nth array.

Thus string array [a, b, c] + string array [1, 2, 3, 4] should yield: {a, 1}, {a, 2}, {a, 3}, {a, 4}, {b, 1}... and adding string array [x, y, z] to the first to would then yield: {a, 1, x}, {a, 1, y}, {a, 1, z} and so forth.

Thanks. I haven't tried the code above, because it operates on strings and Rob's code was just what I needed, but looking over it I think I could have modified it easily. — larsbeck, May 24 '11 at 06:06

score 0 · Accepted Answer · answered May 23 '11 at 14:58

Seems like you want the Cartesian_product. This should work, although I didn't look particularly carefully at edge-cases

public static IEnumerable<T> Drop<T>(IEnumerable<T> list, long numToDrop)
{
    if (numToDrop < 0) { throw new ArgumentException("Number to drop must be non-negative"); }
    long dropped = 0;
    var iter = list.GetEnumerator();
    while (dropped < numToDrop && iter.MoveNext()) { dropped++; }
    while (iter.MoveNext()) { yield return iter.Current; }
}

public static IEnumerable Concat(object head, IEnumerable list)
{
    yield return head;
    foreach (var x in list) { yield return x; }
}

public static IEnumerable<IEnumerable> CrossProduct(IEnumerable<IEnumerable> lists)
{
    if (lists == null || lists.FirstOrDefault() == null) { yield break; }
    var heads = lists.First();
    var tails = CrossProduct(Drop(lists, 1));
    if (tails.FirstOrDefault() == null)
    {
    foreach (var h in heads) { yield return new object[] { h }; }
    }
    else
    {
    foreach (var head in heads)
    {
        foreach (var tail in tails)
        {
        yield return Concat(head, tail);
        }
    }
    }
}

Although as remarked above, Eric Lippert's solution in the question Anthony linked is far prettier. — Rob, May 23 '11 at 15:20
Thanks Rob, this works nicely! Eric's solution is very elegant, I agree, but since I am working with untyped collections I can't use it (or don't know how to). The elements in my collections can be anything from an int to an object, although each collection itself is consistent. — larsbeck, May 24 '11 at 06:04

Generating Permutations for n sets in LINQ

2 Answers2