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:
September 27, 2016 at 3:01 pm
Hey There. I found your blog using msn. This is a very well written article.
I’ll be sure to bookmark it and come back to read more of your useful information. Thanks
for the post. I’ll definitely return.
October 5, 2016 at 9:20 am
Thank you very much, you can also subscribe if you want.
November 24, 2016 at 7:23 pm
This is a great tip particularly to those fresh to the blogosphere.
Simple but very accurate information… Thank
you for sharing this one. A must read post!
January 3, 2017 at 8:01 pm
I have been exploring for a bit for any high-quality articles or blog posts
in this kind of space . Exploring in Yahoo I finally stumbled upon this site.
Studying this information So i am happy to express that I’ve an incredibly
good uncanny feeling I discovered exactly what I needed.
I most surely will make certain to don?t overlook this website and give
it a glance regularly. math solver (Franziska) Mathematics is vital in many areas, including natural research, engineering, medicine, money and the interpersonal sciences.
Applied mathematics has led to totally new mathematical disciplines,
such as information and game theory. Mathematicians take part in pure mathematics also, or mathematics because of its own sake, with no
any application at heart. There is absolutely
no clear range separating clean and applied mathematics, and practical applications
for what commenced as pure mathematics are learned often.