72

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

user2771704
  • 5,994
  • 6
  • 37
  • 38
Chris
  • 39,719
  • 45
  • 189
  • 235

5 Answers5

102

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?

Community
  • 1
  • 1
Eric Lippert
  • 647,829
  • 179
  • 1,238
  • 2,067
  • So would I be correct in saying that this is an alternative to recursive programming? – The Muffin Man Mar 22 '11 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. – Eric Lippert Mar 22 '11 at 17:52
  • That makes sense, however in this question that I asked http://stackoverflow.com/questions/5348485/how-can-i-populate-a-list-box-with-many-categories-using-recursive-programming I could not figure out how to get the result using LINQ without using recursive programming, is there a shorter way? – The Muffin Man Mar 22 '11 at 17:58
  • @Nick: There certainly is. Your problem, as I understand it, is easily solved without recursion. I'll post an answer. – Eric Lippert Mar 22 '11 at 18:33
28

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.

McKay
  • 12,334
  • 7
  • 53
  • 76
  • 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. – Chris Nov 01 '10 at 23:04
  • @Eric Lippert isn't the point of SelectMany to collapse multiple IEnumerable (from various objects of the same type) into one IEnumerable? 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? – McKay Nov 02 '10 at 14:23
  • 3
    That's a lot of questions. (1) isn't the point of SelectMany to collapse multiple IEnumerable into one IEnumerable? 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. – Eric Lippert Nov 02 '10 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 7.16.2.4 of the C# 4.0 specification, which provides a detailed explanation of how to do that translation. – Eric Lippert Nov 02 '10 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! – Eric Lippert Nov 02 '10 at 15:15
  • 2
    (4) Am I missing an operator? No, not to my knowledge. – Eric Lippert Nov 02 '10 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? – Eric Lippert Nov 02 '10 at 15:20
  • @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? – McKay Nov 02 '10 at 17:44
  • "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 }". – Eric Lippert Nov 02 '10 at 18:38
  • 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. – Eric Lippert Nov 02 '10 at 18:41
  • 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. – Eric Lippert Nov 02 '10 at 18:45
  • 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. – McKay Nov 02 '10 at 19:24
16

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
}
Anders Fjeldstad
  • 10,724
  • 2
  • 33
  • 50
  • I actually want all possible combinations of N sets of puppies, but thanks for putting me on the right track. – Chris Nov 01 '10 at 23:02
0

    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);
    }
Software Sith Lord
  • 11
  • 1
-1

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);
Dawid Ireno
  • 49
  • 1
  • 6