Is There a Good Linq Way to Do a Cartesian Product

Is there a good LINQ way to do a cartesian product?

If I understand the question, you want the Cartesian Product of n sets of puppies.

It is easy to get the Cartesian Product if you know at compile time how many sets there are:

from p1 in dog1.Puppies
from p2 in dog2.Puppies
from p3 in dog3.Puppies
select new {p1, p2, p3};

Suppose dog1 has puppies p11, p12, dog2 has puppy p21, and dog3 has puppies p31, p32. This gives you

{p11, p21, p31},
{p11, p21, p32},
{p12, p21, p31},
{p12, p21, p32}

Where each row is an anonymous type. If you do not know at compile time how many sets there are, you can do that with slightly more work. See my article on the subject:

http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/

and this StackOverflow question:

Generating all Possible Combinations

Once you have the method CartesianProduct<T> then you can say

CartesianProduct(from dog in person.Dogs select dog.Puppies)

to get

{p11, p21, p31},
{p11, p21, p32},
{p12, p21, p31},
{p12, p21, p32}

Where each row is a sequence of puppies.

Make sense?

Two approaches to Cartesian product of a collection of lists using LINQ

The first part of the error message is somewhat misleading. The following will compile and work just fine:

var agg = lists.Aggregate(
    new List<List<int>>(),
    (acc, next) 
=>  
    (from ac in acc
    from n in next
    // select ac.Add(n)).ToList());
    select ac.Concat(new[] {n}).ToList()).ToList());

The real problem is with select ac.Add(n). A select clause must return a value (in this case a List<int>), but your call to List<T>.Add modifies the original list and returns void instead.

Under the hood, LINQ tries to transform this LINQ expression into (among other things) a call to Enumerable.SelectMany. One of the arguments the compiler passes is a generated lambda expression that returns ac.Add(n) (i.e. void). The compiler tries to infer the type of the generated lambda based on the available overloads of SelectMany, but there is no compatible overload and so the type of the lambda can't be determined. Hence the error message "Type inference failed in the call to 'SelectMany'.".

Like Add, most List<T> methods aren't generally suitable for functional programming with LINQ, which is why the preferred solution relies only on IEnumerable<T> and its LINQ-related extension methods.

How to get a Cartesian product of a list containing lists?

Here is a LINQ extension method using Aggregate:

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) =>
    sequences.Aggregate(
        Enumerable.Empty<T>().AsSingleton(),
        (accumulator, sequence) => accumulator.SelectMany(
            accseq => sequence,
            (accseq, item) => accseq.Append(item)));

You need the extension method AsSingleton:

public static IEnumerable<T> AsSingleton<T>(this T item) => new[] { item };

This is based on this answer from @EricLippert.

LINQ implementation of Cartesian Product with pruning

You should implement your own IEqualityComparer<IEnumerable<int>> and then use that in Distinct().

The choice of hash code in the IEqualityComparer depends on your actual data, but I think something like this should be adequate if your actual data resemble those in your examples:

class UnorderedQeuenceComparer : IEqualityComparer<IEnumerable<int>>
{
    public bool Equals(IEnumerable<int> x, IEnumerable<int> y)
    {
        return x.OrderBy(i => i).SequenceEqual(y.OrderBy(i => i));
    }

    public int GetHashCode(IEnumerable<int> obj)
    {
        return obj.Sum(i => i * i);
    }
}

The important part is that GetHashCode() should be O(N), sorting would be too slow.

C# Linq - handle outer join and cartesian product

I think this is a trick question because the solution is what you initially expect

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Data;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            DataTable dt = new DataTable();
            dt.Columns.Add("Group", typeof(string));
            dt.Columns.Add("Code", typeof(int));
            dt.Columns.Add("Value", typeof(int));
            dt.Columns["Value"].AllowDBNull = true;

            dt.Rows.Add(new object[] { "GroupA", 13,123});
            dt.Rows.Add(new object[] { "GroupA", 17,456});
            dt.Rows.Add(new object[] { "GroupB", 17,789});

            List<int> codes = dt.AsEnumerable().Select(x => x.Field<int>("Code")).Distinct().ToList();
            var groups = dt.AsEnumerable().GroupBy(x => x.Field<string>("Group")).ToList();

            foreach (var group in groups)
            {
                foreach (int code in codes)
                {
                    if (!group.Any(x => x.Field<int>("Code") == code))
                    {
                        dt.Rows.Add(new object[] { group.Key, code, DBNull.Value });
                    }
                }
            }

        }
    }
}

LINQ cross join list of lists? Cartesian product for unknown number of lists

Answering the question in the title, a product of an unknown number of lists using LINQ:

public static class EnumerableExtensions
{
    public static IEnumerable<IEnumerable<T>> CrossProduct<T>(
        this IEnumerable<IEnumerable<T>> source) => 
        source.Aggregate(
            (IEnumerable<IEnumerable<T>>) new[] { Enumerable.Empty<T>() },
            (acc, src) => src.SelectMany(x => acc.Select(a => a.Concat(new[] {x}))));
}

As far as I understand you want to use it like this:

var beefSteak = GetSteakMenu();
var modifiers = beefSteak.Modifiers.Select(m => m.Options);
var results = modifiers.CrossProduct();

foreach (var resultList in results)
{
    Console.WriteLine($"Steak, {string.Join(", ", resultList.Select(r => r.Name))}");
}

> Steak, Rare, Salad, Beer
> Steak, Medium, Salad, Beer
> Steak, Well done, Salad, Beer
> Steak, Rare, Fries, Beer
> Steak, Medium, Fries, Beer
> Steak, Well done, Fries, Beer
> Steak, Rare, Sweet fries, Beer
> Steak, Medium, Sweet fries, Beer
> Steak, Well done, Sweet fries, Beer
> Steak, Rare, Salad, Wine
> Steak, Medium, Salad, Wine
> Steak, Well done, Salad, Wine
> Steak, Rare, Fries, Wine
> Steak, Medium, Fries, Wine
> Steak, Well done, Fries, Wine
> Steak, Rare, Sweet fries, Wine
> Steak, Medium, Sweet fries, Wine
> Steak, Well done, Sweet fries, Wine
> Steak, Rare, Salad, Coke
> Steak, Medium, Salad, Coke
> Steak, Well done, Salad, Coke
> Steak, Rare, Fries, Coke
> Steak, Medium, Fries, Coke
> Steak, Well done, Fries, Coke
> Steak, Rare, Sweet fries, Coke
> Steak, Medium, Sweet fries, Coke
> Steak, Well done, Sweet fries, Coke

EDIT: Changed the accumulator to use Enumerable.Empty<T>() instead of instantiating an array, as it avoids an allocation.

---

Related Topics