(newbie) N-uples from list of lists

[vd12005]

Hello,

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
plq = plq / len(seq)
for j in range(olen):
si = (j / plq) % len(seq)
outs[j] = seq[si]
for i in range(olen):
outs = tuple(outs)
return outs

many thanx

 

[Dan Bishop]

Hello,

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.

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'])

list(_)

[('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')]

 

[bonono]

Out of curiousity, is "recursion" the desirable way(or is it pythonic
way) ? How would one do it in the imperative way ?

it could be done by a recursive call, but i am interested in using and
understanding generators.

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'])

list(_)

[('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')]

 

[Alex Martelli]

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

 

[bonono]

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>

Thanks, so it seems that it is only doing the "stacking" oneself rather
than relies on the recursive calls(which does the stack for you). Or in
other worlds, a way to get around the recursion limitation but seems to
be harder to understand in this case.

 

[Alex Martelli]

Thanks, so it seems that it is only doing the "stacking" oneself rather
than relies on the recursive calls(which does the stack for you). Or in
other worlds, a way to get around the recursion limitation but seems to
be harder to understand in this case.

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

 

[bonono]

This is my attempt :

def cross(seq):
r=[[]]
for x in seq:
r = [ a + b for a in r for b in [ for i in x ]]
return r

It is not very efficient though as it would loop through the
intermediate list produced multiple times.

 

[vd12005]

great thanks to all.

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 + 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 = wheels.next()
break
except StopIteration:
wheels = iter(sets)
digits = wheels.next()
else:
break

 

[Martin Miller]

FWIW, I found Steven Taschuk's solution easiest to understand regarding
the question posed in your original post -- namely how to solve the
problem non-recursively with generators -- because it was similar to my
own thinking about how to do it -- but suspect that Raymond Hettinger's
is the likely the "best" (as is usually the case ;-).

Best,
-Martin

 

[bonono]

Interesting, I found a reduce one liner(just one step further of
Raymond's) easiest to understand and match my thinking about what the
problem is about.

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.

FWIW, I found Steven Taschuk's solution easiest to understand regarding
the question posed in your original post -- namely how to solve the
problem non-recursively with generators -- because it was similar to my
own thinking about how to do it -- but suspect that Raymond Hettinger's
is the likely the "best" (as is usually the case ;-).

Best,
-Martin

great thanks to all.

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 + 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 = wheels.next()
break
except StopIteration:
wheels = iter(sets)
digits = wheels.next()
else:
break

 

[Martin Miller]

I'd be interested in seeing the one liner using reduce you mentioned --
how it might be done that way isn't obvious to me.

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

====

Interesting, I found a reduce one liner(just one step further of
Raymond's) easiest to understand and match my thinking about what the
problem is about.

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.

FWIW, I found Steven Taschuk's solution easiest to understand regarding
the question posed in your original post -- namely how to solve the
problem non-recursively with generators -- because it was similar to my
own thinking about how to do it -- but suspect that Raymond Hettinger's
is the likely the "best" (as is usually the case ;-).

Best,
-Martin

great thanks to all.

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 + 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 = wheels.next()
break
except StopIteration:
wheels = iter(sets)
digits = wheels.next()
else:
break

 

[bonono]

I'd be interested in seeing the one liner using reduce you mentioned --
how it might be done that way isn't obvious to me.

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, ;-)

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