Cartesian product of multiple sets

What a cartesian product is, knows everyone who ever saw a table. For example:

        |    hard-working        |      lazy        |
| smart | smart and hard-working | smart but lazy   |
| dumb  | dumb but hard-working  | dumb and lazy    |

It’s an example of product of two cartesian sets: {hard-working, lazy} and {smart, dumb}. It’s easy to generate such a product in bash:

maciej@clover ~ $ echo {smart,dumb}-{hard-working,lazy}
smart-hard-working smart-lazy dumb-hard-working dumb-lazy

It’s a list of all the possible pairs of elements.

In order to generate a cartesian product of two sets, one usually writes two nested loops. For example, in Python:

for i in ['smart', 'dumb']:
    for j in ['hard-working', 'lazy']:
        print i, j

What if we want to generate a cartesian product of three sets? Three nested loops? What about four sets? What about N sets?

I’ve found a thread with examples of code generating such cartesian products. I especially liked the solution with generators, because it avoids keeping in memory potentially enormous tables with data. The example from the forum thread:

def cartesian_product(L,*lists):
    if not lists:
        for x in L:
            yield (x,)
        for x in L:
            for y in cartesian_product(lists[0],*lists[1:]):
                yield (x,)+y

It’s a short and effective solution, using recursion. This particular implementation has one distadvantage: lists need to be given as function arguments:

cartesian_product(list1, list2, list3)

I wanted a solution where I could give it a list of lists instead.

UPDATE:  James Hopkin suggested using an asterisk (thanks!):


Here’s my original solution:

def cartesian_product(lists, previous_elements = []):
    if len(lists) == 1:
        for elem in lists[0]:
            yield previous_elements + [elem, ]
        for elem in lists[0]:
            for x in cartesian_product(lists[1:], previous_elements + [elem, ]):
                yield x

Usage of this function can look like this:

a = []
a.append(['in', 'out'])
a.append(['put', 'come'])
for i in cartesian_product(a):
    print "%s%s" % (i[0], i[1])

Another example, generating a natural binary code, with the number of bits as a parameter. Please note that when you give it a very large number of bits, it will take a lot of time to execute, but it will not exhaust the memory.

bits = 5
for i in cartesian_product([range(2) for x in range(bits)]):
    print i

Author: automatthias

You won't believe what a skeptic I am.

2 thoughts on “Cartesian product of multiple sets”

  1. You can use the first version of cartesian_product just by putting * in front of the parameter:

    for i in cartesian_product(*a):

  2. hey i have the same problem right now but only in java

    maybe you also code in java. would you mind if you convert that to java so i can understand

Comments are closed.

%d bloggers like this: