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,)
    else:
        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!):

cartesian_product(*list_of_lists)

Here’s my original solution:

def cartesian_product(lists, previous_elements = []):
    if len(lists) == 1:
        for elem in lists[0]:
            yield previous_elements + [elem, ]
    else:
        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