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

Question

I have an unknown number of buckets(collections), and each bucket having an unknown number of entities

I need to produce a cartesian product of all the entities, so that I endup with a single COLLECTION that has ARRAYS of entities and in each array, there is 1 representetive from EVERY bucket.

So that if I have 5 buckets (B1..B5), and buckets B1, B2 have 1 item each, and bucket B3, B4 and B5 have 4, 8 and 10 items each, I'll have a collection of 320 arrays, and each array will have 5 items.

The only stupud issue here, is that both size of buckets and number of buckets is unknown at development time.

Performance is not super important here, as most of the time, my buckets will have only 1 entity, and only rarely will there be times when some of my buckets will contain 20-30 items...and I'll usually have 5-30 buckets

I'd love to utilize linq here in someway, but my brain is getting fried as I try to imagine how this would work

Answer 1

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

Answer 2

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