Generating a n-ary Cartesian product example

Question

I found that Eric Lippert's post here suits a particular problem I have.

The problem is I can't wrap my head around how I should be using it with a 2+ amount of collections.

Having

var collections = new List<List<MyType>>();
foreach(var item in somequery)
{
    collections.Add(
            new List<MyType> { new MyType { Id = 1} .. n }
        );
}

How do I apply the cartesian product linq query on the collections variabile ?

The extension method is this one:

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

Here is Eric's example for 2 collections:

var arr1 = new[] {"a", "b", "c"};
var arr2 = new[] { 3, 2, 4 };
var result = from cpLine in CartesianProduct(
                     from count in arr2 select Enumerable.Range(1, count)) 
             select cpLine.Zip(arr1, (x1, x2) => x2 + x1);

possible duplicate of [Lists permutations (unknown number)](http://stackoverflow.com/questions/13286882/lists-permutations-unknown-number) — Rawling, Nov 30 '12 at 15:10
@EricLippert 's extension method is far more comprehensible (at least for me) and concise than any of the solutions in those possible duplicates.. — Stefan Anghel, Nov 30 '12 at 15:54

score 5 · Accepted Answer · answered Nov 30 '12 at 20:22

5

The sample code is already able to do "n" cartesian products (it does 3 in the example). Your problem is that you have a List<List<MyType>> when you need an IEnumerable<IEnumerable<MyType>>

IEnumerable<IEnumerable<MyType>> result = collections
  .Select(list => list.AsEnumerable())
  .CartesianProduct();

answered Nov 30 '12 at 20:22

Amy B

108,202
21
135
185

no need to use AsEnumerable() as each List is already an IEnumerable, see: https://stackoverflow.com/a/46327167/1819480 – TermoTux Sep 20 '17 at 16:23
1

@Infinum not quite... the CartesianProduct method takes an `IEnumerable>` If you don't call `AsEnumerable`, you have an `IEnumerable>` which is not compatible. – Amy B Sep 21 '17 at 12:07

score 2 · Answer 2 · answered Jul 09 '21 at 03:56

Much like the original poster of this question, I also had a hard time wrapping my head around the usage of this awesome function. The main thing that caught me was that I had to create this single IEnumerable full of IEnumerable before calling the function (again just like the original post).

The way my code was set up was that I had 3 arrays with data in them that I needed to multiply together, and creating this greater IEnumerable was going out of my way, and I didn't want to do that.

So instead I re-wrote the function to extend off of IEnumerable<T> instead of IEnumerable<IEnumerable<T>> so now I can call the function directly off of any of the arrays that I want to multiply and just pass in the other 2 arrays as parameters. I thought I'd repost here incase anyone else was interested in using it this way:

    public static IEnumerable<IEnumerable<T>> CartesianProduct<T>
    (this IEnumerable<T> firstSequence, params IEnumerable<T>[] sequences)
    {
        IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() };

        foreach (IEnumerable<T> sequence in (new[] { firstSequence }).Concat(sequences))
        {
            result = from resultItem in result 
                     from sequenceItem in sequence 
                     select resultItem.Concat(new[] { sequenceItem });
        }
        return result;
    }

This would be an example of using this method on 3 arrays of data.

        var numbers = new object[] { 1, 2, 3 };
        var letters = new object[] { "a", "b", "c" };
        var colors = new object[] { "red", "blue", "yellow" };

        var result = numbers.CartesianProduct(letters, colors);

The output

        [1, a, red]
        [1, a, blue]
        [1, a, yellow]
        [1, b, red]
        [1, b, blue]
        [1, b, yellow]
        [1, c, red]
        [1, c, blue]
        [1, c, yellow]
        [2, a, red]
        [2, a, blue]
        [2, a, yellow]
        [2, b, red]
        [2, b, blue]
        [2, b, yellow]
        [2, c, red]
        [2, c, blue]
        [2, c, yellow]
        [3, a, red]
        [3, a, blue]
        [3, a, yellow]
        [3, b, red]
        [3, b, blue]
        [3, b, yellow]
        [3, c, red]
        [3, c, blue]
        [3, c, yellow]

Hi @Blake, did you get any OutOfMemory exception when dealing with a large number of items in the sets while calculating CartesianProduct. — manishKungwani, Jan 19 '23 at 12:07

score 0 · Answer 3 · answered Sep 20 '17 at 16:22

Since List<T> is IEnumerable<T>, then your problem using Eric's solution is solved as follows:

var collections = new List<List<MyType>>();
var product =  collections.CartesianProduct();
foreach(var collection in product)
{
    // a single collection of MyType items
    foreach(var item in collection)
    {
        // each item of type MyType within a collection
        Console.Write(item);
    }    
}

Of course you can aggregate the items from each collection in a more concise manner, for example as a single string:

var product = 
    collections
    .CartesianProduct()
    .Select(xs => xs.Aggregate(new StringBuilder(), (sb, x) => sb.Append(x.ToString()), sb => sb.ToString()));

foreach(var collectionAsString in product)
{
    Console.WriteLine(collectionAsString);
}

Generating a n-ary Cartesian product example

3 Answers3

Linked

Related