combinations of variable length nested lists

[Hans Nowak]

>===== Original Message From Mark Robinson <m.1.robinson at herts.ac.uk> =====
>I have hurt my brain (and those who are unfortunate to sit near me ;))
>trying to formulate an algorithm for the following problem. I am sure
>that someone here must be able to help me out, it seems such a trivial
>problem.
>
>I have a nested list structure of the following format:
>[[2, 3, 4, 5],
>  [4, 5, 6, 7, 34],
>  [6, 2, 7, 4]
>  ....
>  ....
>]
>
>I want to generate all possible combinations that take one element from
>each nested list
>
>i.e
>[2, 4, 6, ..., ...]
>[2, 4, 2, ..., ...]
>
>If I knew the length of the outermost list beforehand I could hard code
>it as a series of nested for loops:
>
>i.e
>
>for i in list[0]:
>	for j in list[1]:
>		for k in list[2]:
>				comb = [i, j, k]
>
>but I can't figure a way to do this dynamically at runtime, when the
>outermost list is going to be variable in length.
>
>If anyone can help, I'll be willing to sell my boss into slavery and
>give you all the profit ;)

I already have a boss, but this code may do what you want:

#--- begin code ---

# a test list
lst = [
 [1, 2, 3, 4],
 [5, 6, 7, 8, 9],
 [10, 11],
 [12, 13, 14]
]

def permute2(list1, list2):
    """ Helper function to get the combinations of two lists. """
    permutations = []
    for i in list1:
        for j in list2:
            permutations.append([i, j])
    return permutations

def permute(lst):
    permutations = permute2(lst[0], lst[1])
    for ls in lst[2:]:
        p = []
        # add this list to the permutations list
        for item in ls:
            for perm in permutations:
                p.append(perm + [item])
        permutations = p
    return permutations
    
z = permute(lst)
print z
# check length
assert len(z) == reduce(lambda x, y: x*y, map(len, lst))

# test another
lst = [
    ["a", "b"], ["c", "d", "e"]
]
print permute(lst)

#--- end code ---

Disclaimer: Only roughly tested. I don't know if the term "permutations" is 
correct, aside...

HTH,

--Hans Nowak