generating cross product for list of lists

Question

I have a python list like [[1 2 3] [4 5] [3] [1]] and I want to generate all possible permutations. The output should be something like

[[1 4 3 1] [1 5 3 1] [2 4 3 1] [2 5 3 1] [3 4 3 1] [3 5 3 1]]

I thought about loops but the number of nested loops would vary according to the input. Can someone suggest a good algorithm?

Answer 1

What you want is a carthesian product. itertools has a function product that does exactly that:

import itertools
a = [[1, 2, 3], [4, 5], [3], [1]]
p = itertools.product(*a)
print list(p)

This outputs

[(1, 4, 3, 1),
 (1, 5, 3, 1),
 (2, 4, 3, 1),
 (2, 5, 3, 1),
 (3, 4, 3, 1),
 (3, 5, 3, 1)]