combinations of variable length nested lists
Hans Nowak
hnowak at cuci.nl
Tue Aug 7 16:15:31 CEST 2001
>===== 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
More information about the Python-list
mailing list