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

Question

I have a class structure like so:

Person
Dogs (dog 1, dog 2, etc)
Puppies (puppy A, puppy B, etc)

There is one person. He has 1..n dogs. Each dog has 1..n puppies.

I want a list of all the possible combination of puppies, taking 1 puppy from each dog. Eg:

dog 1 puppy A, dog 2 puppy A dog 1 puppy A, dog 2 puppy B dog 1 puppy B, dog 2 puppy A dog 1 puppy B, dog 2 puppy B

If it was in sql tables, i'd do something like the following to 'multiply' the tables:

select * from puppies a, puppies b where a.parent='dog1' and b.parent='dog2'

Is there some linq-ish way to do this kinda thing???

Thanks so much

Armanda

Answer 1

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?

Introduction

So would I be correct in saying that this is an alternative to recursive programming? – Benedicite

@Nick: I think it would be more germane to say that this is an alternative to imperative programming. The point of LINQ is that you say what you want -- you program declaratively -- and the compiler figures out how to do it based on the runtime libraries available. If those libraries do their work using recursive programming or iterative programming, that's their business. – Introduction

That makes sense, however in this question that I asked #5348985 I could not figure out how to get the result using LINQ without using recursive programming, is there a shorter way? – Benedicite

@Nick: There certainly is. Your problem, as I understand it, is easily solved without recursion. I'll post an answer. – Introduction

Answer 2

dogs.Join(puppies, () => true, () => true, (one, two) => new Tuple(one, two));

You can do a regular join, but the selectors are both returning the same value, because I want all combinations to be valid. When combining, put both into one tuple (or a different data structure of your choosing).

leftSide.SelectMany((l) => rightSide, (l, r) => new Tuple(l, r));

This should do a Cartesian product.

Inside

Thanks a lot. Wow, thats complicated. Goes to show why they invented linq's query comprehension syntax, it certainly is more readable than the fluent in instances like this. – Armanda

@Eric Lippert isn't the point of SelectMany to collapse multiple IEnumerable<T> (from various objects of the same type) into one IEnumerable<T>? After looking over the documentation, I'm not finding a different way to translate your N cartesian product in LINQ without the query syntax. Isn't join defined as a limited set of the cartesian product? Am I missing an operator? Is the from clause only equivalent to a foreach clause, or is there a seperate operator? – Inside

That's a lot of questions. (1) isn't the point of SelectMany to collapse multiple IEnumerable<T> into one IEnumerable<T>? Yes, though of course it does more than just that. From a "sequence" point of view, SelectMany is the cartesian product operator with a projection on the back end. From a more general "monad" point of view, SelectMany is the Bind operation on the monad pattern. – Introduction

(2) "I'm not finding a way to translate the query comprehension Cartesian product to the fluent syntax" - I refer you to section 7.16.2.4 of the C# 4.0 specification, which provides a detailed explanation of how to do that translation. – Introduction

(3) Isn't join defined as a limited set of the Cartesian product? Yes, a join is logically a filter on a Cartesian product. However, that's not how it is implemented. Join is optimized for the equijoin case; the LINQ to Objects implementation aggressively builds hash tables behind the scenes in order to implement the join equality semantics efficiently for cases where the result set is much smaller than the cross product that it is filtering. If what you want is the Cartesian product, then do not use an expensive device designed to filter the Cartesian product; just generate the product! – Introduction

(4) Am I missing an operator? No, not to my knowledge. – Introduction

(5) Is the from clause only equivalent to a foreach clause, or is there a seperate operator? I have no idea what this question means. There is no such thing as a "foreach clause", and I do not know which sets you are describing an equivalence relation on when you say "equivalent". Can you clarify the question? – Introduction

@Eric Lippert (5) Drat, I didn't mean the foreach clause, I meant the foreach operator, and I was asking essentially the same question you answered in #2, but specifically referring to the LINQ syntax. In (1) you mention that it's essentially a cartesian product, so how would you do it with the select many operator? – Inside

"dogs.SelectMany(puppies, (a, b) => new Tuple(a, b))" isn't right. First off, you need a lambda in there: "dogs.SelectMany(dog=>dog.Puppies, (a, b) => new Tuple(a, b))". This is the equivalent of "from dog in dogs from puppy in dog.Puppies select new Tuple(dog, puppy)", which does not give you the cartesian product of two sets of puppies. Rather, this gives you a sequence of (dog, puppy) pairs, one for each puppy of all the dogs. What the OP wants (I think; it is not clear from the question) is "from p1 in dog1.Puppies from p2 in dog2.Puppies select new { p1, p2 }". – Introduction

Basically, the SelectMany operation is only a Cartesian product if the two sets being iterated over are unrelated. If one of the sets is derived from the other, as is the case with there being a parent-child relationship between the dog and the puppies, then SelectMany is actually a generalized concatenation operation with a projection on the end. But we can go farther. Remember, SelectMany is the bind operation on an arbitrary monad. We can build any sequence operation out of SelectMany. – Introduction

For example, "Where" is also just a special case of SelectMany. "from c in cs where b(c) select c" is logically exactly the same as "from c in cs from c2 in b(c) ? new C[] { c } : new C[] { } select c2". "Where" is a special case of SelectMany, Join is a special case of SelectMany, everything is just a special case of SelectMany. We could have built the whole thing out of SelectMany if we we didn't care about performance. All those sequence operators are just optimizations. – Introduction

So I've updated it again. and it should return a cartesian product of leftside and rightside, correct? the first Lambda defines how the two objects are related then? And then the reason there isn't a Cartesian Product operator is that it's not a special special case of SelectMany, because unlike join and where, no additional optimizations are performed. – Inside

Answer 3

If you want all possible combinations of dog and puppy, you would do a cross join:

from dog in Dogs
from puppy in Puppies
select new
{
    Dog = dog,
    Puppy = puppy
}

Whorled

I actually want all possible combinations of N sets of puppies, but thanks for putting me on the right track. – Armanda

Answer 4

    string[] colors = { "Red", "Green", "Blue" };
    string[] sizes = { "Small", "Medium", "Large" };
    
    var result = from color in colors
                 from size in sizes
                 select new { Color = color, Size = size };
    
    foreach (var item in result)
    {
        Console.WriteLine(item);
    }

Lema

Answer 5

I like the idea of McKay, full sample would look like below.

var r = new Random();
var d = Enumerable.Range(1, 3).ToDictionary(x => Guid.NewGuid(), y => Enumerable.Range(1, 10).Select(z => r.Next()).ToList());
var kvps = d.Keys.SelectMany((key) => d[key], (key, value) => new KeyValuePair<Guid, int>(key, value));
var l = kvps.ToLookup(kvp => kvp.Key, kvp => kvp.Value);

Idler

IMO this only adds a lot of noise to a concise method that is clear enough. – Wilma