Cartesian product of lists

Problem Statement:

Given a list of lists of integers, return a list containing the Cartesian product of all the lists of integers.

This is a rather simple but good interview question to test your knowledge of recursion and solving smaller sub-problems.

As an example, given the input [[1,2],[3,4],[5]], the output would be [[1, 3, 5], [1, 4, 5], [2, 3, 5], [2, 4, 5]].

We think about this problem recursively. Given a list of lists of integers L, we can split it at the very last element, so L = [Rest | Last] where Last is a list of integers. The, the Cartesian product of L, is the Cartesian product of the Cartesian product of Rest with Last. The base case of computing the Cartesian product of two lists is simple - it’s just all the ordered pairwise combinations of the two lists.

The above motivates the simple implementation in Python:

# l is a list of lists, for example [[1,2,3],[4,5],[6,7]]
# pre: len(l) >= 2
def cart_prod(l):
 if(len(l) == 2):
   return [ [a,b] for a in l[0] for b in l[1] ]
 else:
   sublist = l[0:len(l)-1] # Everything but the last element
   last = l[-1] # The last element
   sC = cart_prod(sublist) # Cartesian product of the sublist

   return [ a + [b] for a in sC for b in last] # Join the results

We test the above code on the input [[1,2,3],[4,5],[6,7]], and get the correct results

[[1, 4, 6], [1, 4, 7], [1, 5, 6], [1, 5, 7], [2, 4, 6], [2, 4, 7], [2, 5, 6], [2, 5, 7], [3, 4, 6], [3, 4, 7], [3, 5, 6], [3, 5, 7]]