Categories c# cartesian-product linq sql

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


I have a class structure like so:

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


    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:

    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?


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

      Mar 22, 2011 at 17:47

    • 2

      @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.

      Mar 22, 2011 at 17:52

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

      Mar 22, 2011 at 17:58

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

      Mar 22, 2011 at 18:33


    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.


    • 3

      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.

      Nov 2, 2010 at 15:12

    • 3

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

      Nov 2, 2010 at 15:15

    • 3

      (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!

      Nov 2, 2010 at 15:15

    • 2

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

      Nov 2, 2010 at 15:16

    • 2

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

      Nov 2, 2010 at 15:20


    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


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

      – Chris

      Nov 1, 2010 at 23:02