combinations of variable length nested lists

[Joseph A. Knapka]

PEP proposal: add a backtracking Horn-clause resolution
engine to Python!

 :-)

This problem is a two-liner in Prolog:

one_of_each([],[]).
one_of_each([H|T],[H1|Ts]) :- member(H1,H), one_of_each(T,Ts).

It could be quite useful to be able to transparently call
Prolog (or Mercury) from Python. Has anybody done it?
How about Haskell, ML, etc?

-- Joe

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

-- Joe Knapka
"You know how many remote castles there are along the gorges? You
 can't MOVE for remote castles!" -- Lu Tze re. Uberwald
// Linux MM Documentation in progress:
// http://home.earthlink.net/~jknapka/linux-mm/vmoutline.html
2nd Lbl A + 1 = 2nd Pause 2nd Prt GTO 2 R/S