If you are trying to learn about recursion, think this way: The combinations of all the lists consist of taking one item at a time from the first list and prepending this item to all the combinations of the remaining lists.
This way you get
def combinations(rest, prefix = [], result = []):
if rest:
first = rest.pop()
for item in first:
prefix.append(item)
combinations(rest, prefix, result)
prefix.pop()
rest.append(first)
else:
result.append(list(reversed(prefix)))
return result
NB I am far from a Python expert. It's likely there is a more elegant way to code this. Note that because I'm pushing and popping at the ends of lists I need to reverse the final results. The advantage of this is that it's fast and should produce no garbage.
In Idle:
>>> combinations([ [1,2,3],[4,5],[6,7,8,9] ] )
[[1, 4, 6], [2, 4, 6], [3, 4, 6], [1, 5, 6], [2, 5, 6], [3, 5, 6],
[1, 4, 7], [2, 4, 7], [3, 4, 7], [1, 5, 7], [2, 5, 7], [3, 5, 7],
[1, 4, 8], [2, 4, 8], [3, 4, 8], [1, 5, 8], [2, 5, 8], [3, 5, 8],
[1, 4, 9], [2, 4, 9], [3, 4, 9], [1, 5, 9], [2, 5, 9], [3, 5, 9]]