Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

(newbie) N-uples from list of lists

3 views
Skip to first unread message

vd1...@yahoo.fr

unread,
Nov 23, 2005, 8:00:15 PM11/23/05
to
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[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

Dan Bishop

unread,
Nov 24, 2005, 3:03:04 AM11/24/05
to
vd1...@yahoo.fr wrote:
> 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'])
<generator object at 0xb7df072c>
>>> list(_)

bon...@gmail.com

unread,
Nov 24, 2005, 3:08:13 AM11/24/05
to
Out of curiousity, is "recursion" the desirable way(or is it pythonic
way) ? How would one do it in the imperative way ?

Alex Martelli

unread,
Nov 24, 2005, 3:25:47 AM11/24/05
to
bon...@gmail.com <bon...@gmail.com> wrote:

> 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

bon...@gmail.com

unread,
Nov 24, 2005, 3:51:16 AM11/24/05
to
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

unread,
Nov 24, 2005, 4:20:02 AM11/24/05
to
bon...@gmail.com <bon...@gmail.com> wrote:
...

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

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

bon...@gmail.com

unread,
Nov 25, 2005, 5:10:02 PM11/25/05
to
This is my attempt :

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.

vd1...@yahoo.fr

unread,
Nov 29, 2005, 8:53:08 AM11/29/05
to
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 [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

Martin Miller

unread,
Nov 30, 2005, 11:24:52 PM11/30/05
to
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

bon...@gmail.com

unread,
Dec 1, 2005, 2:13:00 AM12/1/05
to
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.

Martin Miller

unread,
Dec 2, 2005, 1:50:12 PM12/2/05
to
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

====

bon...@gmail.com

unread,
Dec 2, 2005, 2:51:03 PM12/2/05
to

Martin Miller wrote:
> 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 :-)

0 new messages