Cartesian Product
September 6, 2013
Today’s exercise is another interview question from our unending supply of interview questions. Beware that it’s a tough one:
Write a function that takes a variable number of lists and returns the cartesian product (sometimes called the cross product) of the items in the lists. For instance, the cartesian product of the lists (1 2 3), (4) and (5 6) is the list of lists ((1 4 5) (1 4 6) (2 4 5) (2 4 6) (3 4 5) (3 4 6)). You should provide both recursive and iterative versions of your function.
Your task is to write the cartesian product function as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
A recursive Haskell version:
cart [] = [[]]
cart (xs:xss) = [ x:ys | x <- xs, ys <- cart xss ]
Simple-minded recursion:
(define (X . sets)
(if (null? sets) '(())
(let ((tails (apply X (cdr sets))))
(apply append
(map (lambda (h)
(map (lambda (t) (cons h t)) tails))
(car sets))))))
;(X '(1 2 3) '(4) '(5 6))
;==> ((1 4 5) (1 4 6) (2 4 5) (2 4 6) (3 4 5) (3 4 6))
Differently iterative:
(define (for-X proc . sets)
(if (null? sets) (proc '())
(for-each
(lambda (head)
(apply for-X (lambda (tail)
(proc (cons head tail)))
(cdr sets)))
(car sets))))
;(for-X write '(1 2 3) '(4) '(5 6)) ==> unspecified
;displays: (1 4 5)(1 4 6)(2 4 5)(2 4 6)(3 4 5)(3 4 6)
A Python version. In Python this functionality is already in library itertools (product).
def product_iteration(*lists): """a simplified copy of the itertools product""" result = [[]] for alist in map(tuple, lists): result = [x + [y] for x in result for y in alist] for prod in result: yield tuple(prod) def product_recursion(*lists): if not lists: yield () else: for alist in lists[0]: for prod in product_recursion(*lists[1:]): yield (alist,) + prod def cartesian(*lists, **kwds): """default: iteration method use method=product_recursion for recursion method """ method = kwds["method"] if "method" in kwds else product_iteration return tuple(method(*lists)) print cartesian([1,2,3], [4],[5,6]) print cartesian([1,2,3], [4],[5,6], method=product_recursion) #->((1, 4, 5), (1, 4, 6), (2, 4, 5), (2, 4, 6), (3, 4, 5), (3, 4, 6))#lang racket (define/match (cartesian-product/r . xss) [('()) '(())] [((cons xs yss)) (for*/list ([ys (apply cartesian-product/r yss)] [x xs]) (cons x ys))]) (define (cartesian-product/i . xss) (map reverse (for/fold ([ps '(())]) ([xs xss]) (for*/list ([p ps] [x xs]) (cons x p)))))Another recursive implementation in Common Lisp:
(defun cartesian-rec (&rest lists) (if (null lists) '(()) (mappend (lambda (x) (mapcar (lambda (lst) (cons x lst)) (apply #'cartesian-rec (cdr lists)))) (car lists))))And, for fun, here is one with macros, generating a separate loop for every level:
(defun cartesian-loops (lst vars) (if (null lst) `(push (list ,@(reverse vars)) acc) (let ((v (gensym))) `(dolist (,v ,(car lst)) ,(cartesian-loops (cdr lst) (cons v vars)))))) (defmacro cartesian (&rest lists) `(let ((acc '())) ,(cartesian-loops lists '()) (nreverse acc)))Here is an iterative and recursive C# solution:
public interface ICartesianProduct { int[][] GetProduct(int[][] sets); } public class CartesianProductIterative : ICartesianProduct { public int[][] GetProduct(int[][] inputSets) { var resultSetCount = 1; foreach (var s in inputSets) { resultSetCount *= s.Length; } var resultSets = new int[resultSetCount][]; var resultCounter = 0; // Create initial set of cartesian products built from the last set from the input for (int j = 0; j < inputSets[inputSets.Length - 1].Length; j++) { resultSets [j] = new int[inputSets.Length]; resultSets [j] [inputSets.Length - 1] = inputSets [inputSets.Length - 1] [j]; resultCounter++; } // Build up all remaining sets in the cartesian product for (int i = inputSets.Length - 2; i >= 0; i--) { // Inject first item in set [i], into previous built cartesian product sets for (int j = 0; j < resultCounter; j++) { resultSets [j] [i] = inputSets [i] [0]; } // create new copies of all cartesian sets previously built (up to sets [i-1]) - but swap out the // items in the current set [i] so all items in set [i] have been enumerated for (int j = 1; j < inputSets[i].Length; j++) { for (int k = 0; k < resultCounter; k++) { int newIdx = (resultCounter * j) + k; resultSets [newIdx] = new int[inputSets.Length]; Array.Copy (resultSets [k], i + 1, resultSets [newIdx], i + 1, inputSets.Length - (i + 1)); resultSets [newIdx] [i] = inputSets [i] [j]; } } resultCounter *= inputSets[i].Length; } return resultSets; } } public class CartesianProductRecursive : ICartesianProduct { public int[][] GetProduct(int[][] sets) { var resultSets = new List<int[]> (); var indices = new int[sets.Length]; CreateProductSet (sets, indices, 0, resultSets); return resultSets.ToArray(); } private void CreateProductSet(int[][] inputSets, int[] indices, int currentSet, List<int[]> resultSets) { for (int i = 0; i < inputSets[currentSet].Length; i++) { indices [currentSet] = i; if (currentSet == (inputSets.Length - 1)) { var cartesianSet = new int[inputSets.Length]; for (int j = 0; j < inputSets.Length; j++) { cartesianSet[j] = (inputSets[j][indices[j]]); } resultSets.Add (cartesianSet); } else { CreateProductSet (inputSets, indices, currentSet + 1, resultSets); } } } }Haskell doesn’t really have functions with variable numbers of arguments, and faking such is more for programmers of Okasaki’s caliber than mine, so I’ll just have it take a list of lists. I started out with a recursive solution, then realized I could make it a little prettier:
Then I looked on the Internet for advice. Oddly enough, it turns out that Haskell has Cartesian products in the Prelude, but not in an obvious way.
does the trick. It took me a while to figure out how it works, so I figured I’d type up my reasoning below:
sequence is actually a rather more general. Here’s how it’s defined at http://hackage.haskell.org/package/base-4.6.0.1/docs/src/Control-Monad.html#sequence
-- | Evaluate each action in the sequence from left to right, -- and collect the results. sequence :: Monad m => [m a] -> m [a] {-# INLINE sequence #-} sequence ms = foldr k (return []) ms where k m m' = do { x <- m; xs <- m'; return (x:xs) }The funky return [] can immediately be rewritten based on the instance declaration for lists in http://hackage.haskell.org/package/base-4.6.0.1/docs/src/GHC-Base.html#Monad partially copied below:
m >>= k = foldr ((++) . k) [] m return x = [x]In particular, note that return [] is actually the same as [[]]. Also, for lists, we can translate the do notation directly to list comprehension notation, so the above definition for sequence, specialized to lists, is written much more transparently thus:
sequence :: [[a]] -> [[a]] sequence ls = foldr k [] ms where k m m' = [x:xs | x <- m, xs <- m']Now it’s much clearer what is going on: this is just translating the Cartesian product of [l1,l2,…,ln] into l1*(l2*(l3*…)).
Now how is that do notation or list comprehension treated under the hood? Well, it’s translated to
Now what does that funky >>= do? Well, m >>= k is foldr ((++).k) [] m, which is not immediately helpful. But letting m=[m1,m2,…,mn] and expanding the foldr simplifies things a drop:
It’s still a tad weird, though. What the heck is (++).k? It’s a function, obviously, that takes a value, applies k to it, and then applies (++) to the result. Writing this out, it’s
or, equivalently,
That is, p `(++).k` q = k(p) ++ q.
Substituting this in, m >>= k becomes much simpler:
so we’re just applying k to each of the elements of m and concatenating the results!
So
just means that for each element x of m, for each element xs of m’ we form the list [x:xs], concatenate these together to form [x:xs1++x:xs2++…], and concatenate those together to form [x1:xs1++x1:xs2++…++x2:xs1++x2:xs2++…], which is the Cartesian product.
Which is the Cartesian product of x with xs, I should say. Now that I understand what the helper function “k” in sequence does, the operation of sequence becomes clear.