Recursive "all paths" through a list of lists - Python
python, recursion
Solution
is there a solution to this that uses itertools module?
Yes, and it's pretty simple with `itertools.product()`. This is sufficient for your specific example...
>>> import itertools
>>> l = [['a', 'b'], 'c', ['d', 'e'], ['f', 'g'], 'h']
>>> for i in itertools.product(*l): print list(i)
['a', 'c', 'd', 'f', 'h']
['a', 'c', 'd', 'g', 'h']
['a', 'c', 'e', 'f', 'h']
['a', 'c', 'e', 'g', 'h']
['b', 'c', 'd', 'f', 'h']
['b', 'c', 'd', 'g', 'h']
['b', 'c', 'e', 'f', 'h']
['b', 'c', 'e', 'g', 'h']
...but as DSM pointed out in the comments, it only works because your example uses one-character strings, which are sequence objects of length one. If this is always the case, you could express the list like this...
['ab', 'c', 'de', 'fg', 'h']
However, in the general case, you'd probably want to ensure all the list items are sequences with something like this...
>>> l = [None, int, 0, 'abc', [1, 2, 3], ('a', 'b')]
>>> for i in itertools.product(*[i if isinstance(i, (list, tuple)) else [i] for i in l]): print list(i)
[None, <type 'int'>, 0, 'abc', 1, 'a']
[None, <type 'int'>, 0, 'abc', 1, 'b']
[None, <type 'int'>, 0, 'abc', 2, 'a']
[None, <type 'int'>, 0, 'abc', 2, 'b']
[None, <type 'int'>, 0, 'abc', 3, 'a']
[None, <type 'int'>, 0, 'abc', 3, 'b']
any other, better approach to this particular problem? like non-recursive solution, faster solution, less memory-intensive one?
Any solution would probably have to use recursion in some way, if not on the stack, then on the heap.
Problem
A peculiar problem, given a list of lists (nested at most one level here): ``` [['a', 'b'], 'c', ['d', 'e'], ['f', 'g'], 'h'] ``` ..find all the lists of length the same as given list and containing all the possible combinations of elements from sublists, with exactly 1 element of a given sublist at the same position as original sublist (it's hard to even put this in words). That is, find this: ``` ['a', 'c', 'd', 'f', 'h'] ['a', 'c', 'd', 'g', 'h'] ['a', 'c', 'e', 'f', 'h'] ['a', 'c', 'e', 'g', 'h'] ['b', 'c', 'd', 'f', 'h'] ['b', 'c', 'd', 'g', 'h'] ['b', 'c', 'e', 'f', 'h'] ['b', 'c', 'e', 'g', 'h'] ``` Now, I have found the solution, but it's not satisfactory for me: ``` def all_paths(s, acc=None, result=None): # not using usual "acc = acc or []" trick, because on the next recursive call "[] or []" would be # evaluated left to right and acc would point to SECOND [], which creates separate accumulator # for each call stack frame if acc is None: acc = [] if result is None: result = [] head, tail = s[0], s[1:] acc_copy = acc[:] for el in head: acc = acc_copy[:] acc.append(el) if tail: all_paths(tail, acc=acc, result=result) else: result.append(acc) return result ``` As you can see, it involves copying accumulator list TWICE, for rather obvious reason that if .append() or .extend() method gets called down the recursion stack, accumulator would get modified since it is passed by label (sharing in official lingo?). I tried to cook up solution that pop()s and append()s relevant number of items off accumulator, but can't get it right: ``` def all_p(s, acc=None, result=None, calldepth=0, seqlen=0): if acc is None: acc = [] if result is None: seqlen = len(s) result = [] head, tail = s[0], s[1:] for el in head: acc.append(el) if tail: all_p(tail, acc=acc, result=result, calldepth=calldepth+1, seqlen=seqlen) else: result.append(acc[:]) print acc for i in xrange(1+seqlen-calldepth): acc.pop() return result ``` Result: ``` ['a', 'c', 'd', 'f', 'h'] ['a', 'c', 'd', 'g', 'h'] ['a', 'c', 'd', 'e', 'f', 'h'] ['a', 'c', 'd', 'e', 'g', 'h'] ['a', 'c', 'd', 'e', 'b', 'c', 'd', 'f', 'h'] ['a', 'c', 'd', 'e', 'b', 'c', 'd', 'g', 'h'] ['a', 'c', 'd', 'e', 'b', 'c', 'd', 'e', 'f', 'h'] ['a', 'c', 'd', 'e', 'b', 'c', 'd', 'e', 'g', 'h'] ['a', 'c', 'd', 'f', 'h'] ['a', 'c', 'd', 'g', 'h'] ['a', 'c', 'd', 'e', 'f', 'h'] ['a', 'c', 'd', 'e', 'g', 'h'] ['a', 'c', 'd', 'e', 'b', 'c', 'd', 'f', 'h'] ['a', 'c', 'd', 'e', 'b', 'c', 'd', 'g', 'h'] ['a', 'c', 'd', 'e', 'b', 'c', 'd', 'e', 'f', 'h'] ['a', 'c', 'd', 'e', 'b', 'c', 'd', 'e', 'g', 'h'] ``` Obviously, this is because as depth-first recursion here jumps up and down the call chain and I can't get the number of pop()s right to finetune the accumulator list. I do realize that this is of little practical gain as copying the list is O(n) while popping k items off a list is O(k), so there isn't all that much difference here, but I'm curious if this can be accomplished. (Background: I'm redoing phonecode benchmark, http://page.mi.fu-berlin.de/prechelt/phonecode/, and this is the part that finds all the words, but each fraction of a phone number can map to several words, like so: ``` ... '4824': ['fort', 'Torf'], '4021': ['fern'], '562': ['mir', 'Mix'] ... ``` so I need to find all the possible "paths" through a selected list of matching words and/or digits, corresponding to given phone number) Questions, requests: can the version that does not copy accumulator be fixed? is there a solution to this that uses itertools module? any other, better approach to this particular problem? like non-recursive solution, faster solution, less memory-intensive one? Yes I know this is a truckload of problems, but if somebody solves a non-empty subset of them I'd be grateful. :-)