i think it could be done by using itertools functions even if i can not
see the trick. i would like to have all available "n-uples" from each
list of lists.
example for a list of 3 lists, but i should also be able to handle any
numbers of items (any len(lol))
lol = (['a0', 'a1', 'a2'], ['b0', 'b1'], ['c0', 'c1', 'c2', 'c3'])
=>
[('a0', 'b0', 'c0'), ('a0', 'b0', 'c1'), ('a0', 'b0', 'c2'), ('a0',
'b0', 'c3'), ('a0', 'b1', 'c0'), ('a0', 'b1', 'c1'), ('a0', 'b1',
'c2'), ('a0', 'b1', 'c3'), ('a1', 'b0', 'c0'), ('a1', 'b0', 'c1'),
('a1', 'b0', 'c2'), ('a1', 'b0', 'c3'), ('a1', 'b1', 'c0'), ('a1',
'b1', 'c1'), ('a1', 'b1', 'c2'), ('a1', 'b1', 'c3'), ('a2', 'b0',
'c0'), ('a2', 'b0', 'c1'), ('a2', 'b0', 'c2'), ('a2', 'b0', 'c3'),
('a2', 'b1', 'c0'), ('a2', 'b1', 'c1'), ('a2', 'b1', 'c2'), ('a2',
'b1', 'c3')]
maybe tee(lol, len(lol)) can help ?
it could be done by a recursive call, but i am interested in using and
understanding generators.
i also have found a convenient function, here :
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/65285 (paste
below)
but i am curious of how you will do it or refactorize this one with
generators...
def permuteflat(*args):
outs = []
olen = 1
tlen = len(args)
for seq in args:
olen = olen * len(seq)
for i in range(olen):
outs.append([None] * tlen)
plq = olen
for i in range(len(args)):
seq = args[i]
plq = plq / len(seq)
for j in range(olen):
si = (j / plq) % len(seq)
outs[j][i] = seq[si]
for i in range(olen):
outs[i] = tuple(outs[i])
return outs
many thanx
def cross(*args):
"""Iterates over the set cross product of args."""
if not args:
return
elif len(args) == 1:
for x in args[0]:
yield (x,)
else:
for x in args[0]:
for y in cross(*args[1:]):
yield (x,) + y
>>> cross(['a0', 'a1', 'a2'], ['b0', 'b1'], ['c0', 'c1', 'c2', 'c3'])
<generator object at 0xb7df072c>
>>> list(_)
> Out of curiousity, is "recursion" the desirable way(or is it pythonic
> way) ? How would one do it in the imperative way ?
For an inherently recursive problem (as this one appears to be), the
traditional alternative to recursion is maintaining your own LIFO stack.
If (with all the obvious refactorings) things gets messy, ah well, at
least you've broken free of the recursion limit;-). [[ Sometimes
(rarely) things don't get messy, and then you find out that the problem
wasn't really "inherently recursive";-) ]]
An example of recursion elimination in Python can be found at
<http://mail.python.org/pipermail/python-list/2002-January/082481.html>
Alex
Yep, that's recursion elimination for you -- once in a while it will
guide you to a "truly" nonrecursive solution that you had not
considered, but mostly it's just an optimization (in almost ANY
language, generally -- recursion in most languages stacks up everything
whether it needs to or not, with elimination you get to stack up the
minimal needed amount of state, so it can be faster) fully including the
"obfuscation" typical of optimizations;-)
Alex
def cross(seq):
r=[[]]
for x in seq:
r = [ a + b for a in r for b in [[i] for i in x ]]
return r
It is not very efficient though as it would loop through the
intermediate list produced multiple times.
actually i have not seen it was a cross product... :) but then there
are already few others ideas from the web, i paste what i have found
below...
BTW i was unable to choose the best one, speaking about performance
which one should be prefered ?
### --------------------------------------------------
### from title: variable X procuct - [(x,y) for x in list1 for y in
list2]
### by author: steindl fritz
### 28 mai 2002
### reply by: Jeff Epler
def cross(l=None, *args):
if l is None:
# The product of no lists is 1 element long,
# it contains an empty list
yield []
return
# Otherwise, the product is made up of each
# element in the first list concatenated with each of the
# products of the remaining items of the list
for i in l:
for j in cross(*args):
yield [i] + j
### reply by: Raymond Hettinger
def CartesianProduct(*args):
ans = [()]
for arg in args:
ans = [ list(x)+[y] for x in ans for y in arg]
return ans
"""
print CartesianProduct([1,2], list('abc'), 'do re mi'.split())
"""
### from:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/159975
### by: Raymond Hettinger
def cross(*args):
ans = [[]]
for arg in args:
ans = [x+[y] for x in ans for y in arg]
return ans
### from:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/159975
### by: Steven Taschuk
"""
Iterator version, Steven Taschuk, 2003/05/24
"""
def cross(*sets):
wheels = map(iter, sets) # wheels like in an odometer
digits = [it.next() for it in wheels]
while True:
yield digits[:]
for i in range(len(digits)-1, -1, -1):
try:
digits[i] = wheels[i].next()
break
except StopIteration:
wheels[i] = iter(sets[i])
digits[i] = wheels[i].next()
else:
break
Best,
-Martin
That once again tell me that different people think and approach the
problem differently. It is possible to talk about one "fastest" way,
but many times there isn't such a thing of one "best" way.
Another aspect of Taschuk's solution I like and think is important is
the fact that it is truly iterative in the sense that calling it
returns a generator which will yield each of the combinations, one at
time. All the others create and return all the combinations at once
(as I suspect the one liner using reduce you mention does, too).
As you point out, "best" is always in the eyes of the beholder.
"Best" regards, ;-)
-Martin
====
def combine_lol(seq): return reduce(lambda x,y: (a+(b,) for a in x for
b in y), seq, [()])
I use generator expression but being a reduce, it will still goes all
the way till the last sequence before you can have any output. That is
the nature of the problem anyway. You can use scanl equivalent to have
intermediate result if the problem allows but I don't that is true in
this case.
The python community is quite against this kind of thing and treat
map/filter/reduce as plague, it is described as ugly/messy :-)