Drawing Blanks

Premature Optimization is a Prerequisite for Success

Cross-join of enumerators

leave a comment »

Exploring new C# language features, inspired by my ex-coworkers.
How do we compute a cartesian product (cross-join) in modern C#? Of course we want to avoid intermediate storage allocations. And of course arrays with integer indexes are out of fashion.
For a fixed number of sets, a simple LINQ query does a nice job.
var result =
               from n1 in set1
               from n2 in set2
               from n3 in set3
               select new { n1, n2, n3 }; 
 
And what if we have a set of sets? My solution is below. But here’s a problem: it only joins sets of the same type T. Can we support multiple types and still be strong-typed? Linq kind of does that! And of course treating everything as object is not cool.
 

IEnumerable<IEnumerable<T>> CartesianProduct<T>(IEnumerable<IEnumerable<T>> setOfSets)

{

var head = setOfSets.First();

var tail = setOfSets.Skip(1);

bool isTailEmpty = !tail.Any();

if (isTailEmpty)
   foreach (T x in head)
    yield return Singlet(x);
else
  foreach (var set in CartesianProduct(tail))
foreach (T x in head)
  yield return set.Concat(Singlet(x));
}
IEnumerable<T> Singlet<T>(T x) {yield return x; }
Advertisements

Written by bbzippo

11/05/2009 at 3:54 pm

Posted in programming

Tagged with

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

%d bloggers like this: