# Cartesian product of lists

#### Posted on August 11, 2013

##### Last updated on August 13, 2013

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:

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

Markdown SHA1: 5836f9131a47779ebd38bf25d947b669be97d242