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#?

Answer 1

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

Answer 2

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