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

Answer 1

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.

Answer 2

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
}

Answer 3

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?