LINQ Short Takes – Number 2 – Using Method Syntax to Create a Cartesian Product


Introduction

This is the second post in a series (I have no idea how many blog posts this series may comprise) of LINQ Short Takes. The first post was LINQ Short Takes – Number 1 – Enumerable.Range() which presented the Enumerable.Range() method. This blog post utilises the Enumerable.Range() method to form a Cartesian product utilising the LINQ method syntax (see: MSDN (Microsoft Developer Network Web Site) Article – LINQ Query Syntax versus Method Syntax (C#)for further discussion of the topic).

The motivation for developing this approach was twofold:

1. I did need a sequence of integers that formed a Cartesian product.

2. I experienced a degree of exasperation, frustration and downright ‘that’s wrong and very tacky’ when I looked for LINQ Cartesian Products using Method syntax. The solutions I read used a SelectMany()and lacked clarity that any good code should have.

So, I decided that there must be a simpler way to form a Cartesian product from two sequences using LINQ method calls. What has resulted is a solution to the problem that, in my opinion, is clear and concise. The solutions implementation uses a LINQ Join() method call to build the Cartesian product.

Cartesian Products

Please excuse the diversion into a little bit set theory. This diversion explains why the LINQ Join() method succeeds in forming a Cartesian product.

A Cartesian productis a resulting sequence of two input sequences. The output sequence has that all elements in the first sequence join with each element of the second sequence. The resulting sequence is series of element pairs from both input sequences. The length of the output sequence is the product of the lengths of the two input sequences.

The join operation between the two sequences that form the Cartesian producthas the following properties. If all of the elements in the two input sequences match each other, we have a type of join with a special property. This type of join’s special property implies that the join key for all of the elements in the two sequences is the same value.

Armed with the conclusion that a Cartesian product has the join key for both inputs sequences should be the same value. The process of forming a C# statement which utilises the Join() method to form a Cartesian product between the two input sequences becomes a simple process.

Example Code

The following C# method contains three examples of forming a Cartesian product. I will comment a little more on the three examples after the code.

The code also utilises the LINQ extension method ToOutput. This was the subject of a previous blog post: Dumping a formatted IEnumerable to Output.

I have loaded this code in Work docx and pfd formats as well. The URL’s are:
https://craigwatson1962.files.wordpress.com/2012/02/cartesianproducts.docx
https://craigwatson1962.files.wordpress.com/2012/02/cartesianproducts.pdf

private void CartesianProducts()
{
    // Query Syntax Cartesian Product var Prod1 = from num1 in Enumerable.Range(0, 10)
                from num2 in Enumerable.Range(0, 10)
                select new { num1, num2 };
    Debug.WriteLine("/nDump of Prod1");
    // Dump the contents of Prod1 Prod1.ToOutput(FormatFunction:
        (objValue, Position) =>
        {
            return string.Format("[{0}] {1},{2}\n",
                Position, objValue.num1, objValue.num2);
        });

    // Generate a Cartesian product using LINQ method syntax from two sequences var Prod2 = Enumerable.Range(0, 10).Join(Enumerable.Range(0,10),
        (iVal1) => 1, // Key selectors make all elements in first sequence (iVal2) => 1, // match all elements in the second sequence. (iVal1, iVal2) =>
            new {iVal1, iVal2}); // Create an object with the two values. Debug.WriteLine("/nDump of Prod2");
    // Dump the contents of Prod2 Prod2.ToOutput(FormatFunction:
        (objValue, Position) =>
        {
            return string.Format("[{0}] {1},{2}\n",
                Position, objValue.iVal1, objValue.iVal2);
        });

    string[] SampleStrings = new string[]
    { "The", "quick", "red", "fox", "jumped",
        "over", "the", "lazy", "brown", "cow" };
    // Generate a 3 way Cartesian product var Prod3 = Enumerable.Range(0, 10)
                    .Join(Enumerable.Range(0, 5), iVal1 => 1, iVal2 => 1,
                        (iVal1, iVal2) => new { iVal1, iVal2 })
                    .Join(SampleStrings, iVals => 1, strVals => 1,
                        (iVals, strVal) =>
                            new {
                                intValue1 = iVals.iVal1,
                                intValue2 = iVals.iVal2,
                                strValue = strVal });
    Debug.WriteLine("/nDump of Prod3");
    // Dump the contents of Prod3 Prod3.ToOutput(FormatFunction:
        (objVal, Position) =>
            string.Format("[0] {1},{2},'{3}'\n",
                Position, objVal.intValue1, objVal.intValue2, objVal.strValue));
    Debug.WriteLine(string.Format(
        "Double Check\n\tSequence1 Length {0} Sequence2 Length {1}" +
        "SampleStrings Length{2}\n\t" +
        "Input Sequence Product Value {3} Result Length {4}",
        Enumerable.Range(0, 10).Count(),
        Enumerable.Range(0, 5).Count(),
        SampleStrings.Count(),
        Enumerable.Range(0, 10).Count()
            * Enumerable.Range(0, 5).Count()
            * SampleStrings.Count(),
        Prod3.Count()));

    return;
}

The examples of forming a Cartesian product with LINQ are:

  1. This example uses the LINQ query syntax to create a Cartesian product. It uses an unconstrained join between the two sequences. This is exactly how SQL operates when used to form a Cartesian product.
  2. The second example uses the LINQ method syntax to form a Cartesian product between two integer sequences. These sequences are generated using the Enumerable.Range () method. The Cartesian product is formed using the LINQ method Join(). The arguments to the overload of the Join() methods are: the second IEnumerable, the outer (first sequence) key selector, the inner (the second sequence) key selector, and the result selector. The key selectors in each part of the join are just 1, which ‘says’ this is the join key for each of the same sequences.
  3. The third example demonstrates the scalability of the approach, by joining three sequences in a Cartesian product. If you can do this with two, and three sequences, then I would expect the approach would work with as many sequences as you require. This example also demonstrates the joining of different types of object using this approach.

If you missed it above, this example method also uses the ToOutput LINQ extension method. The ToOutput extension method was the subject of a previous blog post: Dumping a formatted IEnumerable to Output, and the code for the extension method is included there.

Conclusions

  • I believe that the approach presented is a clear, clean, and concise, approach to generation of a Cartesian product using the LINQ method syntax.
  • I suspect that I will generalise this approach into another LINQ extension method. The may well become another blog post. There are a couple of interesting deign decisions which I need to make when designing and implementing this approach as an extension method. I will leave those discussions for that blog post.

, , , , , , , ,

  1. LINQ Pivot, or Crosstab, Extension Method « Craig's Eclectic Blog
  2. LINQ Extension Method to Generate n-way Cartesian Product « Craig's Eclectic Blog
  3. LINQ Short Takes – Number 3 –LINQ over Multiple Dimension Arrays and Lists « Craig's Eclectic Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: