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
```

2007-05-25 at 17:24 |

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

for i in cartesian_product(*a):

2008-07-21 at 18:02 |

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