combinations of variable length nested lists

[Mark Robinson]

Thanks alot Hans,

that looks great, just gonna take a closer look in a minute. I have 
actually (I think) come up with the following solution, but it is 
recursive, and I am not sure I am comfortable with that :s

def comb(list, *pos):
    if not pos:
       pos = 0
   else:
       pos = pos[0]
   newList = []
   for each in list[pos]:
       if pos < len(list)-1:
           fromNext = comb(list, pos+1)
           for item in fromNext:
               temp = [each]
               for subitem in item:
                   temp.append(subitem)
               newList.append(temp)
       else:
           newList.append([each])
   return newList

combList = comb(list)

actually it is really great to see how you thought about the problem, 
cos I was really unable to think outside of the box so to speak..



cheers

blobby


Hans Nowak wrote:

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