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

Jane

So you're trying to create all of the possible combinations of 5 items that occur when selecting one item from each of the buckets? – Janina

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

Arbour

Need to try this out, but your result is exactly what i want – Jane

Is this a permutation (order matters) or a combination (order doesn't matter)? – Gaines

Answer 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

Serinaserine

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

Adult

Answer 4

Another LINQ-based option, based on suggestion from Diego, but more precise in terms of argument and return types. It also does not require multiple enumerations of outer collection and hence does not produce Resharper's hint "Possible multiple enumerations".

public static IEnumerable<IReadOnlyCollection<T>> GetPermutations<T>(
    IEnumerable<IReadOnlyCollection<T>> collections) =>
        collections
            .Aggregate(
                new[] { Array.Empty<T>() },
                (acc, next) =>
                    acc
                        .SelectMany(accItem =>
                            next.Select(nextItem => accItem.Concat(new[] { nextItem }).ToArray()))
                        .ToArray());

Broderickbrodeur

Answer 5

This is probably a very late answer, but I encounter a similar problem i.e. generate all permutations of a list of list of string. However, in my problem, I don't need all permutations simultaneously. I only need/generate next permutation if current permutation doesn't satisfy my condition. Therefore, the following is my way of doing a kind of "for each" and with conditional continuation during permutations generation. This answer is inpsired by Tom19's answer.

void ForEachPermutationDo<T>(IEnumerable<IEnumerable<T>> listOfList, Func<IEnumerable<T>, bool> whatToDo) {
    var numCols = listOfList.Count();
    var numRows = listOfList.Aggregate(1, (a, b) => a * b.Count());
    var continueGenerating = true;

    var permutation = new List<T>();
    for (var r = 0; r < numRows; r++) {
        var repeatFactor = 1;
        for (var c = 0; c < numCols; c++) {
            var aList = listOfList.ElementAt(c);
            permutation.Add(aList.ElementAt((r / repeatFactor) % aList.Count()));
            repeatFactor *= aList.Count();
        }

        continueGenerating = whatToDo(permutation.ToList()); // send duplicate
        if (!continueGenerating) break;

        permutation.Clear();
    }
}

Using the above method, generating all permutation can be done like

IEnumerable<IEnumerable<T>> GenerateAllPermutations<T>(IEnumerable<IEnumerable<T>> listOfList) {
    var results = new List<List<T>>();

    ForEachPermutationDo(listOfList, (permutation) => {
        results.Add(permutation);
        return true;
    });

    return results;
}

Skewness