IanG on Tap

I recently found myself needing to solve a problem that involved producing an n-ary Cartesian product. I ended up with a fun solution in which I used LINQ to generate a LINQ query. I thought I’d share it. Being me, I spent quite a while writing a blog about this, tinkering with the details, and leaving it for a few days so I could re-read the text with a fresher point of view. And then I got distracted. And then it got so large that I split it up.

The problem with sitting on a draft of a blog post for that long is that there’s a good chance that Eric Lippert will write a post on exactly the same topic in between me starting to write the post and actually publishing it.

Ah well. I ended up with a slightly different solution from Eric. Also, the main reason I was delaying this was that I wanted to get a couple of examples from other languages together. So I hope this will be interesting even to people who have already read Eric’s post.

This ended up being rather longer than I had anticipated, so I’m breaking it up into a series.

• Simple but Too Specialized (this entry)
• Moving Away from Anonymous Types
• LINQ to LINQ
• The Missing LINQ: IEnumerable<T> and Scalars
• Other Languages
• Closing Thoughts

Part 1 – Simple but Too Specialized

Before getting to the general n-ary case, let’s start with a simple case: the Cartesian product of two sets, or a cross join, as it’s known in databases. If you’re not familiar with this operation, it just produces every possible pairing between the items from two sets. This is easy in C# thanks to LINQ:

char[] letters = { 'A', 'B', 'C' };
int[] numbers = { 1, 2, 3, 4 };

var cartesianProduct = from letter in letters
                       from number in numbers
                       select new { letter, number };

foreach (var item in cartesianProduct)
{
    Console.WriteLine(item);
}

I start with two lists—the letters A, B, and C, and the numbers 1-4—and the output shows all the possible pairs:

{ letter = A, number = 1 }
{ letter = A, number = 2 }
{ letter = A, number = 3 }
{ letter = A, number = 4 }
{ letter = B, number = 1 }
{ letter = B, number = 2 }
{ letter = B, number = 3 }
{ letter = B, number = 4 }
{ letter = C, number = 1 }
{ letter = C, number = 2 }
{ letter = C, number = 3 }
{ letter = C, number = 4 }

That’s fine as far as it goes, but I needed to deal with more than two lists. LINQ can handle this too—you can have as many from clauses as you like:

char[] letters = { 'A', 'B', 'C' };
int[] numbers = { 1, 2, 3, 4 };
string[] colours = { "Red", "Blue" };

var cartesianProduct = from letter in letters
                       from number in numbers
                       from colour in colours
                       select new { letter, number, colour };

This produces the following output:

{ letter = A, number = 1, colour = Red }
{ letter = A, number = 1, colour = Blue }
{ letter = A, number = 2, colour = Red }
{ letter = A, number = 2, colour = Blue }
{ letter = A, number = 3, colour = Red }
{ letter = A, number = 3, colour = Blue }
{ letter = A, number = 4, colour = Red }
{ letter = A, number = 4, colour = Blue }
{ letter = B, number = 1, colour = Red }
{ letter = B, number = 1, colour = Blue }
{ letter = B, number = 2, colour = Red }
{ letter = B, number = 2, colour = Blue }
{ letter = B, number = 3, colour = Red }
{ letter = B, number = 3, colour = Blue }
{ letter = B, number = 4, colour = Red }
{ letter = B, number = 4, colour = Blue }
{ letter = C, number = 1, colour = Red }
{ letter = C, number = 1, colour = Blue }
{ letter = C, number = 2, colour = Red }
{ letter = C, number = 2, colour = Blue }
{ letter = C, number = 3, colour = Red }
{ letter = C, number = 3, colour = Blue }
{ letter = C, number = 4, colour = Red }
{ letter = C, number = 4, colour = Blue }

That’s a 3-way Cartesian product. You can keep adding as many from clauses as you like, because LINQ supports n-ary Cartesian products. Problem solved? Not quite. This approach is perfect if you know how many sets you’re combining at compile time—in these examples, I knew what the ‘n’ in n-ary was when writing the code. (2, and 3, respectively.)

But in the problem I’m trying to solve, I didn’t have that information at compile time. I need to produce the n-ary Cartesian product across a bunch of sets where I don’t know how many sets there would be until runtime.

But this doesn’t stop me from using LINQ. A LINQ query is just an object built up by a series of method calls—the query expression syntax I used in the last couple of examples disguises this, but explicit method calls offer a bit more power. LINQ queries with multiple from clauses use the SelectMany operator beneath the covers, so that last query is equivalent to this:

var lettersAndNumbersCartesianProduct = letters.SelectMany(
    letter => numbers.Select(number => new { letter, number }));

var cartesianProduct = lettersAndNumbersCartesianProduct.SelectMany(
    (letterAndNumber) => colours.Select(colour =>
        new { letterAndNumber.letter, letterAndNumber.number, colour }));

More generally, if you have N from clauses you will have N-1 calls to SelectMany. (You’ll notice that I’ve now got two anonymous types—the one used to contain the pairs produced by the first SelectMany is fed into the second SelectMany that produces the (letter, number, colour) ‘triples’ that make up my final output. One of the advantages of using the C# query expression syntax is that the C# compiler hides all of this sort of stuff for you. If you inspect the code C# produces for the query expression version, using ILDASM or Reflector, you’ll see it’s doing something similar under the covers.)

I split the last example into two statements to highlight a useful fact: if I need a 3-way Cartesian product, I can start with a 2-way Cartesian product, and then just bolt an extra SelectMany on the end. This technique of taking an existing LINQ query and invoking an extra operator on it to form a more complex query is sometimes called chaining.

I can take this a step further and build a general purpose method that takes any number ‘n’ of sets and produces the n-ary Cartesian product of those sets by repeatedly chaining SelectMany calls. However, I’d need to come up with a slightly more adaptable representation. As it stands, with each set I add to the product, the resulting set’s members grow more complex. The Cartesian product of numbers and letters produced a set where each member had both a number and a letter, e.g. { letter = 'A', number = 2 } or { letter = 'C', number = 1 }. The Cartesian product of numbers letters, and colours produced a set where each member had three items, looking like { letter = A, number = 3, colour = "Red" } or { letter = B, number = 2, colour = "Blue" }.

I’ll have to abandon anonymous types to generalize this—anonymous types are great when you know at compile time exactly what you’ll be dealing with. But they cannot adapt at runtime. So in the next blog in this series, I’ll use a different representation, so that I can write a generalized method for producing an n-ary Cartesian product.