Create all combinations of n*m values

Question

Say I have a data structure of IEnumerable<IEnumerable<object>> like this:

{
    { A, B }
    { 1, 2, 3 }
    { Z }
}

Where the outer array can contain any number of inner arrays. And the inner arrays can each independently contain any number of elements. And assume, for the sake of simplicity, that no array will be empty.

And I want to transform it to a IEnumerable<IEnumerable<object>> like this:

{ { A, 1, Z }, { A, 2, Z }, { A, 3, Z }, { B, 1, Z }, { B, 2, Z }, { B, 3, Z } }

Which contains every combination of the values from the original structure. So each element in each inner array maps by index to an element/array in the original outer array.

What is the simplest way to do that in C#?

I think this question will help you: [calculate the number of combinations to form 100](http://stackoverflow.com/questions/3510586/algorithm-to-calculate-the-number-of-combinations-to-form-100) — Matt Ellen, Apr 15 '11 at 10:41

score 22 · Accepted Answer · answered Apr 15 '11 at 10:45

22

You could use CartesianProduct method by Eric Lippert for this (taken from here):

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

answered Apr 15 '11 at 10:45

Oleks

31,955
11
77
132

1

I've not tested the solution - but the answer given is very elegant. Almost Prolog-esque in fact! – pb. Apr 15 '11 at 16:24
Is it possible to write a code in Java? Is there a link? – Jay Patel Nov 26 '15 at 01:55
@JayPatel: here is a similar question and [answer](http://stackoverflow.com/a/4240323/102112) but in Java – Oleks Nov 26 '15 at 06:43

score 2 · Answer 2 · answered Apr 15 '11 at 10:53

private static IEnumerable<IEnumerable<object>> GetAllCombinations(IEnumerable<IEnumerable<object>> a)
    {
        if (!a.Skip(1).Any())
        {
            return a.First().Select(x => new[] { x });
        }

        var tail = GetAllCombinations(a.Skip(1)).ToArray();
        return a.First().SelectMany(f => tail.Select(x => new[] { f }.Concat(x)));
    }

Create all combinations of n*m values

2 Answers2

Linked

Related