Computing a Cartesian Product with LINQ

re: Computing a Cartesian Product with LINQ

Tyler — Tue, 27 Nov 2012 10:56:00 GMT

Is there any chance of this being written in TSQL?

re: Computing a Cartesian Product with LINQ

gautam — Wed, 17 Oct 2012 17:42:41 GMT

Can you give example input structure and code that calls this method?

re: Computing a Cartesian Product with LINQ

Senthil_Benasainnce — Mon, 20 Feb 2012 15:48:17 GMT

I am getting outofmemory exception when I am trying to compute cartesian product of 10 array (each has 100 items). I am getting this in the middle of computation. Is it possible to clean up the memory in the middle and let the accumulator use the unused memory?

re: Computing a Cartesian Product with LINQ

Mikael — Wed, 07 Dec 2011 07:40:05 GMT

This blogpost just saved my day.

Thank you!

re: Computing a Cartesian Product with LINQ

Brook — Fri, 02 Sep 2011 01:26:15 GMT

Totally awesome! Thank you for helping me out bigtime!

re: Computing a Cartesian Product with LINQ

Dave — Fri, 09 Jul 2010 20:19:46 GMT

@Jarno: Good catch, I changed it to ns.Skip(1).

@bman654: You're right, that fixes it. I understand now, basically .NET only defers the evaluation of the enumerable elements... it does not defer method application unless explicitly told to do so (with the EnumerableEx.Defer method). So when the sequence defintion is recurisvle defined, it will stack overflow because of the method application (that is, the recurive call). It works in Haskell becuase the opposite is true there, everything is defered unless explicitly told not to do so.

Thanks.

re: Computing a Cartesian Product with LINQ

bman654 — Thu, 08 Jul 2010 03:11:57 GMT

@Dave: Your GetPrimes method is infinitely recursive and overflows the stack while building the LINQ expression.

Try using EnumerableEx.Defer() from the Reactive framework. Something like this might work for you:

return ns.Take(1).Concat(EnumerableEx.Defer(() => GetPrimes(ns.Where(n => n % p != 0))));

re: Computing a Cartesian Product with LINQ

Jarno Peschier — Wed, 07 Jul 2010 05:46:00 GMT

Article makes perfect sense: excellent functional programming example, I think.

@Szindbad: If you have unit tests to verify functional behavior and the method is documented nobody should give a rats ass about the implementation and if they can (immediately) understand it, right? Just because you don't understand it (as the "average" team member) doesn't mean the writer didn't understand. Or the team cannot use the code and and benefit?

@Dave: This works fine as far as I know (I've worked succesfully with infinate return values like your From() function). Aren't you using the whole sequence again in you "return ns.Take(1).Concat(GetPrimes(ns.Where(n => n % p != 0)));"? Shouldn't that second ns be ns.Skip() or something? As in ns = x:xs and you're doing the where clause on ns instead of just on xs?

re: Computing a Cartesian Product with LINQ

Sjoerd Visscher — Tue, 06 Jul 2010 12:20:20 GMT

Instead of var s = sequence, you can probably also switch the froms:

foreach(var sequence in sequences)

{

// recursive case: use SelectMany to build the new product out of the old one

result =

from item in sequence

from seq in result

select seq.Concat(new[] {item});

}

re: Computing a Cartesian Product with LINQ

Dave — Thu, 01 Jul 2010 22:36:17 GMT

gotta love that cartesian product, this reminded me of some code I'd written to find prime numbers using the Sieve of Eratosthenes once. It's not meant to be uber efficent or anything, just call it a programming challenge. I wrote it like so:

sealed class Program

{

static IEnumerable<BigInteger> GetPrimes(IEnumerable<BigInteger> ns)

{

var p = ns.First();

return ns.Take(1).Concat(GetPrimes(ns.Where(n => n % p != 0)));

}

static IEnumerable<BigInteger> From(BigInteger n)

{

while (true) { yield return n++; }

}

static void Main(string[] args)

{

var two = new BigInteger(2);

var primes = GetPrimes(From(two));

foreach (var p in primes.Take(10)) { Console.WriteLine(p); }

}

But it goes into infinite recursion and blows the stack to pieces (how's that for StackOverflow). Anyway, it works just fine in Haskell:

Prelude> let primes = let sieve (x:xs) = x:sieve [y | y <- xs, y `mod` x /= 0] in sieve [2..]

Prelude> take 10 primes

[2,3,5,7,11,13,17,19,23,29]

Haskell has non-strict semantics (lazy) and C# doesn't but it is supposed to for IEnumerable... best I could conclude is that Haskell is "more lazy" than C#. Anyone have a more concrete explanation?