Cartesian product of lists

One of the patterns of problem solving in programming is the Exhaustive Search. This is simply saying that to find a solution to a specific problem, you have to search all the possible solutions and validate them based on some constraints. It’s not the most optimal strategy of solving problems, but there are cases when you don’t have any choice.

Think, for example, of this simple problem. Given two lists of numbers, how do you combine their elements in every possible way?

More concrete, you’re given the lists: [1,2,3] and [4,5]. The task is to enumerate all the possible ways in which you can choose a single element from the first list to be paired with a single element from the second list.The pattern of choices is as in the following image:

In this way, we’ve constructed all the pairs needed: [1,4], [2,4], [3,4], [1,5], [2,5], [3,5]. This is called the cartesian product of lists. Generally, given two sets A and B, the cartesian product AxB = {(a,b) | a is in A, b is in B}.

Why is so important the cartesian product of lists?

Let’s say you work with a given matrix M and you want to find all the possible matrices (starting from M) with a given property. Take, for example, the matrix below (we’ll refer to it as the matrix M):

1  0

0  4

Let’s restrict M and say that 0 can be only 1,2,3 or 4. How do you proceed to generate all the matrices (starting from M) by instantiating 0 with the values from the list [1..4]?

A first solution would be to represent the matrix as an array of rows (which are also arrays). That will suggest to loop through the rows unsing indices, which is not very elegant.

A second solution would be to represent the matrix as of list of rows (which are also lists). In this case, we have the opportunity to use the device of cartesian product of lists to generate all the possible choices. This is more elegant and much more easy to manipulate mathematically.

More concrete, the matrix M is encoded like this: M = [ [1,0], [0,4] ] (the list of rows). In order to be able to use the cartesian product of lists, we need to represent every possible choice like this:

• a digit d <> 0 will become a singleton list [d].
• a digit d = 0 will become the list of choices [1,2,3,4] = [1..4]

in this way we’ll have the matrix S = [ [ [1], [1..4] ], [ [1..4], [4] ] ]. We can distinguish now the internal elements:

L1 =  [ [1], [1..4] ] and L2 = [ [1..4], [4] ].

If we apply cartesian product on L1 and L2, we obtain all the possible rows, and from all the possible rows, if we apply the cartesian product, we obtain all the possible matrices derived from M with the restriction that 0 could be any element of [1..4].

For example, cartesian product applied to L1 will result in L11 = [ [1,1], [1,2] ,[1,3], [1,4] ]. Doing the same with L2, we obtain L21 = [ [1,4], [2,4], [3,4], [4,4]].

Now we only have to apply the cartesian product on L11 and L21 and we obtain all the matrices derived from M with the restriction that 0 can be only from the list [1..4]

• choice 1: M1 = [ [1,1], [1,4] ]
• choice 2: M2 = [ [1,2], [1,4] ]
• choice 3: M3 = [ [1,3], [1,4] ]
• etc.

How to construct the cartesian product of lists?

Let’s start, again, with an example. We’ll denote cartesian product on lists by cartprod.

cartprod [ [2], [1,3]] = [ [2,1], [2,3] ]

But how to construct cartprod [ [1,2], [2], [1,3] ]? From cartprod [ [1,2], [2], [1,3] ] = [ [1,2,1], [1,2,3], [2,2,1], [2,2,3] ] we observe that basically what we’ve done is the following:

• take 1 from the [1,2] and prefix to the elements of cartprod [ [2], [1,3]]
• take 2 from the [1,2] and prefix to the elements of cartprod [ [2], [1,3]]

That being said, we can formalize it with a list comprehension:

cartprod :: [[a]] -> [[a]];
cartprod [] = [[]]
cartprod (xs:xss) = [x:ys | x<- xs, ys <-yss]
where yss = cartprod xss

This definition says nothing more than split the list in head and tail (xs = [1,2] = head and [ [2], [1,3]] = tail = xss), compute the cartesian product of the tail in yss, and prefix each element x from the head to each element of yss.

As a final remark, cartesian product of lists is a very powerful method to implement exhaustive search, so it’s worth knowing and understanding it!

This blog post is a more elaborate explanation of a part of Richard Bird’s Sudoku solver. If you want to read more about this, you can find it in Richard Bird’s book:

Constantin Liculescu