Cartesian products, part 1

I was recently tasked with finding a solution to a particularly wonky problem that challenged me algorithmically, and I figured I'd write a little post on the experience. The fact that as software developers we are surrounded by a cornucopia of libraries, frameworks, gems, jars, etc. - while certainly beneficial to our execution of our craft - means that the opportunity to solve a really *interesting* problem comes up relatively rarely. So when I was given the job of finding all possible combinations of 1 element each from n distinct sets of varying length and contents (i.e the Cartesian product of n sets), I leapt at the opportunity to flex my long-underutilized comp-sci muscles. The problem and my own solution are given in detail below, with a few caveats: 1) If you don't like math, well, you should. :P 2) I wholeheartedly reserve the right to be wrong, and if you know a better way to acquire the same result, please email me!

So, here's the problem:

Given n distinct sets X_{1}, X_{2}, ... X_{n}, find all possible sets consisting of n elements, one from each set. Such a result is known as the Cartesian product, and can be represented mathematically as:

P = \prod_{j=1}^{n}X_{j} = X_{1}\times X_{2}\times ...X_{n}

where P is the actual product. What does this product look like? Let's see an example.

We'll say we have two sets X_{1} and X_{2}:

X_{1} = \{a, b\}
X_{2} = \{1, 2\}

The Cartesian product of these two sets would be a "set of sets", or more formally a collection or family of sets, and would look like the following:

P = X_{1}\times X_{2} = \{\{a,1\},\{a,2\},\{b,1\},\{b,2\}\}

As you can see if you examine the above, for each element of set X_{1}, there are exactly two sets in the result that contain that element - each of which also contains one or the other element of X_{2}. We have our product. Now let's figure out how we got here - and we'll start with the easy-to-compute question: How many possible combinations can there be?

Well, this is likely the easiest problem in combinatorics there is to solve. Remember above where we stated the formula for arriving at a Cartesian product?

P = \prod_{j=1}^{n}X_{j} = X_{1}\times X_{2}\times ...X_{n}

Well, the number we're particularly after is the cardinality of the final collection P. In this context, the word "cardinality" means "size" - i.e. the cardinality of any set is the number of elements in that set. In mathematical notation, we represent the cardinality of a set by surrounding the name of the set by two vertical bars - very similar to what you may know as the notation for absolute value. So, the cardinality of the set X_{1} above would be represented as \left|X_{1}\right| and would be equal to 2, because set X_{1} has exactly 2 elements, a and b. So, given what we now know about cardinality, how do we use that to compute the cardinality of P, or \left|P\right|? It literally couldn't be easier:

\left|P\right| = \prod_{j=1}^{n}\left|X_{j}\right| = \left|X_{1}\right|\times \left|X_{2}\right|\times ...\left|X_{n}\right|

That's right - you just multiply the cardinalities of all the sets in question together, and voilá: you have how many combinations there would be. Now, we've already stated that the cardinalty \left|X_{1}\right| of set X_{1} is equal to two, and it should be plain by now that the cardinality \left|X_{2}\right| of set X_{2} is also equal to two. As such, that would give us the answer 4 for \left|P\right|, and lo and behold, the result set P shown above has exactly 4 elements!

Now to the harder bit - how do we figure out precisely what those elements are? Enter my good friend and soon-to-be yours (if he isn't already), recursion. Below I have implemented the algorithm I worked out - though I make no claims to it being a heretofore undiscovered one - as a pure function (i.e. a function "without side-effects", which does not alter any external state) in Ruby, my programming language of choice. Note how the method calls itself as part of its execution - that's recursion.

def cartesian_product(*enums)
  return Set.new([Set.new]) if enums.empty?
  combos = Set.new
  first = enums.shift
  subproducts = cartesian_product(*enums)
  subproducts.each do |product|
    first.each do |element|
      combos.add(product.clone.add(element))
    end
  end
  combos
end

So there's the meat of the matter - more explanation to come in part 2, coming soon!

Attempt #4

OK. This time, I'm going to do it, and do it right. This time, I will become a prolific, opinionated, and sought-after blogger. This time, I will write more than a half-hearted rant condemning regular expressions and half a tutorial on a subject hardly anybody cares about. This time, I'm doing it right.

That's science - so stay tuned.

Return top