Dynamically cross-join multiple different-size collections together in Linq (C#)

Solution 1:

You could create an extension method like the following:

public static class EnumerableExtensions
{
    public static IEnumerable<TValue []> Permutations<TKey, TValue>(this IEnumerable<TKey> keys, Func<TKey, IEnumerable<TValue>> selector)
    {
        var keyArray = keys.ToArray();
        if (keyArray.Length < 1)
            yield break;
        TValue [] values = new TValue[keyArray.Length];
        foreach (var array in Permutations(keyArray, 0, selector, values))
            yield return array;
    }

    static IEnumerable<TValue []> Permutations<TKey, TValue>(TKey [] keys, int index, Func<TKey, IEnumerable<TValue>> selector, TValue [] values)
    {
        Debug.Assert(keys.Length == values.Length);

        var key = keys[index];
        foreach (var value in selector(key))
        {
            values[index] = value;
            if (index < keys.Length - 1)
            {
                foreach (var array in Permutations(keys, index+1, selector, values))
                    yield return array;
            }
            else
            {
                yield return values.ToArray(); // Clone the array;
            }
        }
    }
}

As an example, it could be used like:

    public static void TestPermutations()
    {
        int [][] seqence = new int [][]
        {
            new int [] {1, 2, 3},
            new int [] {101},
            new int [] {201},
            new int [] {301, 302, 303},
        };

        foreach (var array in seqence.Permutations(a => a))
        {
            Debug.WriteLine(array.Aggregate(new StringBuilder(), (sb, i) => { if (sb.Length > 0) sb.Append(","); sb.Append(i); return sb; }));
        }
    }

and produce the following output:

1,101,201,301
1,101,201,302
1,101,201,303
2,101,201,301
2,101,201,302
2,101,201,303
3,101,201,301
3,101,201,302
3,101,201,303

Is that what you want?

Solution 2:

Here's how to do it without recursion in a single Linq statement (wrapped around an extension method for convenience):

public static IEnumerable<IEnumerable<T>> GetPermutations<T>(
                     IEnumerable<IEnumerable<T>> listOfLists)
{
    return listOfLists.Skip(1)
        .Aggregate(listOfLists.First()
                .Select(c => new List<T>() { c }),
            (previous, next) => previous
                .SelectMany(p => next.Select(d => new List<T>(p) { d })));
}

The idea is simple:

1. Skip the first row, so we can use it as the initial value of an aggregate.
2. Place this initial value in a list that we'll grow on each iteration.
3. On each iteration, create a new list for each element in previous and add to it each of the elements in next (this is done by new List<T>(p) { d }).

EXAMPLE

Suppose you have an array of arrays as follows:

var arr = new[] {
  new[] { 1,2 },
  new[] { 10,11,12 },
  new[] { 100,101 }
};

Then arr.GetPermutations() will return a list of lists containing:

1,10,100
1,10,101
1,11,100
1,11,101
1,12,100
1,12,101
2,10,100
2,10,101
2,11,100
2,11,101
2,12,100
2,12,101

Solution 3:

Non-Linq, non-recursive solution that's faster. We pre-allocate the entire output matrix and then just fill it in a column at a time.

T[][] Permutations<T>(T[][] vals)
{
    int numCols = vals.Length;
    int numRows = vals.Aggregate(1, (a, b) => a * b.Length);

    var results = Enumerable.Range(0, numRows)
                            .Select(c => new T[numCols])
                            .ToArray();

    int repeatFactor = 1;
    for (int c = 0; c < numCols; c++)
    {
        for (int r = 0; r < numRows; r++)
            results[r][c] = vals[c][r / repeatFactor % vals[c].Length];
        repeatFactor *= vals[c].Length;
    }

    return results;
}