Creating unique combinations from lists

[breal]

I have three lists... for instance

a = ['big', 'small', 'medium'];
b = ['old', 'new'];
c = ['blue', 'green'];

I want to take those and end up with all of the combinations they
create like the following lists
['big', 'old', 'blue']
['small', 'old', 'blue']
['medium', 'old', 'blue']
['big', 'old', 'green']
['small', 'old', 'green']
['medium', 'small', 'green']
['big', 'new', 'blue']
['small', 'new', 'blue']
['medium', 'new', 'blue']
['big', 'new', 'green']
['small', 'new', 'green']
['medium', 'new', 'green' ]

I could do nested for ... in loops, but was looking for a Pythonic way
to do this. Ideas?

 

[Reedick, Andrew]

-----Original Message-----
From: [email protected] [mailtoython-
[email protected]] On Behalf Of breal
Sent: Wednesday, January 16, 2008 2:15 PM
To: (e-mail address removed)
Subject: Creating unique combinations from lists

I have three lists... for instance

a = ['big', 'small', 'medium'];
b = ['old', 'new'];
c = ['blue', 'green'];

I want to take those and end up with all of the combinations they
create like the following lists
['big', 'old', 'blue']
['small', 'old', 'blue']
['medium', 'old', 'blue']
['big', 'old', 'green']
['small', 'old', 'green']
['medium', 'small', 'green']
['big', 'new', 'blue']
['small', 'new', 'blue']
['medium', 'new', 'blue']
['big', 'new', 'green']
['small', 'new', 'green']
['medium', 'new', 'green' ]

I could do nested for ... in loops, but was looking for a Pythonic way
to do this. Ideas?

http://www.python.org/dev/peps/pep-0202/

 

[breal]

-----Original Message-----
From: [email protected] [mailtoython-
[email protected]] On Behalf Of breal
Sent: Wednesday, January 16, 2008 2:15 PM
To: (e-mail address removed)
Subject: Creating unique combinations from lists

I have three lists... for instance

a = ['big', 'small', 'medium'];
b = ['old', 'new'];
c = ['blue', 'green'];

I want to take those and end up with all of the combinations they
create like the following lists
['big', 'old', 'blue']
['small', 'old', 'blue']
['medium', 'old', 'blue']
['big', 'old', 'green']
['small', 'old', 'green']
['medium', 'small', 'green']
['big', 'new', 'blue']
['small', 'new', 'blue']
['medium', 'new', 'blue']
['big', 'new', 'green']
['small', 'new', 'green']
['medium', 'new', 'green' ]

I could do nested for ... in loops, but was looking for a Pythonic way
to do this. Ideas?

http://www.python.org/dev/peps/pep-0202/

Thanks for the reply. I never realized you could use list
comprehension like this... AWESOME!

 

[Martin v. Löwis]

I could do nested for ... in loops, but was looking for a Pythonic way

to do this. Ideas?

I find nested for loops very Pythonic. Explicit is better than implicit,
and simple is better than complex.

Regards,
Martin

 

[Tim Chase]

a = ['big', 'small', 'medium'];

b = ['old', 'new'];
c = ['blue', 'green'];

I want to take those and end up with all of the combinations they
create like the following lists
['big', 'old', 'blue']
['small', 'old', 'blue']
['medium', 'old', 'blue']
['big', 'old', 'green']
['small', 'old', 'green']
['medium', 'small', 'green']
['big', 'new', 'blue']
['small', 'new', 'blue']
['medium', 'new', 'blue']
['big', 'new', 'green']
['small', 'new', 'green']
['medium', 'new', 'green' ]

I could do nested for ... in loops, but was looking for a Pythonic way
to do this. Ideas?

You can use a recursive generator:

def iterall(*iterables):
if iterables:
for head in iterables[0]:
for remainder in iterall(*iterables[1:]):
yield [head] + remainder
else:
yield []

for thing in iterall(
['big', 'medium', 'small'],
['old', 'new'],
['blue', 'green'],
):
print thing

The two for-loops plus recursion should handle any number of
parameters, so if you were so inclined, you could do

for thing in iterall(
['big', 'medium', 'small'],
['old', 'new'],
['blue', 'green'],
['smelly', 'fragrant'],
['spatula', 'avocado'],
):
print thing

and get all 3*2*2*2*2 items. Or count in binary:

for i, bitstream in enumerate(iterall(
[0, 1],
[0, 1],
[0, 1],
[0, 1],
[0, 1],
[0, 1],
)):
print ''.join(map(str, bitstream)), '=', i

When you're iterating over combinations of items in groups of
lists, I prefer the clarity of this over something like

[(a,b,c,d,e) for a in [0,1] for b in [0,1] for c in [0,1] for
d in [0,1] for e in [0,1]]


-tkc

 

[Matimus]

I have three lists... for instance

a = ['big', 'small', 'medium'];
b = ['old', 'new'];
c = ['blue', 'green'];

I want to take those and end up with all of the combinations they
create like the following lists
['big', 'old', 'blue']
['small', 'old', 'blue']
['medium', 'old', 'blue']
['big', 'old', 'green']
['small', 'old', 'green']
['medium', 'small', 'green']
['big', 'new', 'blue']
['small', 'new', 'blue']
['medium', 'new', 'blue']
['big', 'new', 'green']
['small', 'new', 'green']
['medium', 'new', 'green' ]

I could do nested for ... in loops, but was looking for a Pythonic way
to do this. Ideas?

I would probably just create a generator:

def permute(a,b,c):
for x in a:
for y in b:
for z in c:
yield [x,y,z]

all_combos = list(permute(
['big', 'small', 'medium'],
['old', 'new'],
['blue', 'green']))

print all_combos


I'm using nested for loops, but I sure find it easy to read that way.
Though, using list comprehension does pretty much the same thing. It
appears that Tim Chase has posted a more generic version of the above.

Matt

 

[Steven D'Aprano]

I could do nested for ... in loops, but was looking for a Pythonic way
to do this. Ideas?

What makes you think nested loops aren't Pythonic?

 

[Tim Chase]

I could do nested for ... in loops, but was looking for a Pythonic way

What makes you think nested loops aren't Pythonic?

On their own, nested loops aren't a bad thing. I suspect they
become un-Pythonic when they make code look ugly and show a
broken model of the problem. There's a big diffence between:

# iterate over a 10x10 grid
for i in xrange(10):
for j in xrange(10):
print i,j

which is pretty manageable, but quickly becomes very unpythonic
if the problem is poorly defined:

for a in range(5):
for b in range(5):
for c in range(5):
for d in range(5):
for e in range(5):
for f in range(5):
for g in range(5):
for h in range(5):
for i in range(5):
for j in range(5):
for k in range(5):
for l in range(5):
for m in range(5):
for n in range(5):
for o in range(5):
for p in range(5):
for q in range(5):
for r in range(5):
for s in range(5):
for t in range(5):
for u in range(5):
for v in range(5):
for w in range(5):
for x in range(5):
for y in range(5):
for z in range(5):
print a,b,c,d,e,f,g,
print h,i,j,k,l,m,n,
print o,p,q,r,s,t,u,
print v,w,x,y,z

It gets even worse if your loop nesting is based on something
external. You wouldn't want code that looks like

if len(input) == 2:
for a in range(5):
for b in range(5):
whatever(a,b)
elif len(input) == 3:
for a in range(5):
for b in range(5):
for c in range(5):
whatever(a,b,c)
elif len(input) == 4:
...

Contributing to the unpythonic'ness (unpythonicity?) of it is
that something is clearly happening at a higher level than just
for-loops so other Python constructs should be used to express
them instead of abusing your code to do your dirty work.

-tkc

 

[zugnush]

for a in range(5): ....
for z in range(5):

means the inner loop runs 5**26 times so perhaps it's not only
unpythonic but also uncomputable...

 

[Tim Chase]

for a in range(5):

...

means the inner loop runs 5**26 times so perhaps it's not only
unpythonic but also uncomputable...

only if you're impatient

yes, it was a contrived pessimal example. It could be range(2)
to generate boolean-number sequences. I've done 2**26 loops in
code before (well, it was on the way to 2**32, just to see how
long it took to roll over and hit an error condition).

The main emphasis was to show that there was a pattern unfolding
that should have been translated into more pythonic code than
just hard-coding nested loops.

-tkc

 

[Martin v. Löwis]

The main emphasis was to show that there was a pattern unfolding that

should have been translated into more pythonic code than just
hard-coding nested loops.

Practicality beats purity. That you would solve a more general problem
in a more general way doesn't mean that you shouldn't solve the more
specific problem (combinations from three sets) in a specific,
easy-to-read way. Readability counts.

I find your solution (with nested generators) *very* unpythonic. It
is much more complicated than necessary to solve the problem at hand,
and it doesn't get Pythonic just by using the latest language features.
It may be a smart solution, but not a Pythonic one.

Regards,
Martin

P.S. To solve the general problem, I like

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496807

 

[Reedick, Andrew]

-----Original Message-----

From: [email protected] [mailtoython-
[email protected]] On Behalf Of Tim Chase
Sent: Wednesday, January 16, 2008 3:40 PM
To: breal
Cc: (e-mail address removed)
Subject: Re: Creating unique combinations from lists

You can use a recursive generator:

def iterall(*iterables):
if iterables:
for head in iterables[0]:
for remainder in iterall(*iterables[1:]):
yield [head] + remainder
else:
yield []

for thing in iterall(
['big', 'medium', 'small'],
['old', 'new'],
['blue', 'green'],
):
print thing

Recursion definitely makes for an elegant solution. However you do take
a bit of a performance hit. If performance matters (and comprehensions
are supposed to be optimized/fast) and you want a "works for N nested
loops solution," then you could build a N deep comprehension on the fly
and eval() it:


def gen(lists):
out = '[' + ','.join(["v%s" % i for i in range(len(lists))]) +
']'
comp = ''.join([ " for v%d in lists[%d]" % (i, i) for i in
range(len(lists))])
return eval('[ ' + out + comp + ' ]')

gen([a, b, c])


So for a three item list, it would build and execute the following
comprehension:
[ [v0,v1,v2] for v0 in lists[0] for v1 in lists[1] for v2 in
lists[2] ]
Seven item list:
[ [v0,v1,v2,v3,v4,v5,v6] for v0 in lists[0] for v1 in lists[1]
for v2 in lists[2] for v3 in lists[3] for v4 in lists[4] for v5 in
lists[5] for v6 in lists[6] ]


Some rough performance numbers in seconds for 1,000 iterations over a
three item list:
list comprehension: 0.74
nested for loop : 0.97 31% slower
recursion : 3.91 428% slower =P
eval : 1.11 50% slower





from timeit import Timer

s = "a = [ i for i in range(10) ]; b = a; c = a"

t = Timer( "l = [ [i, j, k] for i in a for j in b for k in c]", s)

iterations = 1000

print "list comprehension: %4.2f" % t.timeit(iterations)


t = Timer('''
l = []
for i in a:
for j in b:
for k in c:
l.append([i, j, k])
''', s)

print "nested for loop : %4.2f" % t.timeit(iterations)


t = Timer('''
def iterall(*iterables):
if iterables:
for head in iterables[0]:
for remainder in iterall(*iterables[1:]):
yield [head] + remainder
else:
yield []

for thing in iterall(a, b, c):
pass #print thing
''', s)

print "recursion : %4.2f" % t.timeit(iterations)


t = Timer('''
def gen(lists):
out = '[' + ','.join(["v%s" % i for i in range(len(lists))]) +
']'
comp = ''.join([ " for v%d in lists[%d]" % (i, i) for i in
range(len(lists))])
return eval('[ ' + out + comp + ' ]')
gen([a, b, c])
''', s)

print "eval : %4.2f" % t.timeit(iterations)



*****

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from all computers. GA621

 

[Tim Chase]

You can use a recursive generator:

def iterall(*iterables):
if iterables:
for head in iterables[0]:
for remainder in iterall(*iterables[1:]):
yield [head] + remainder
else:
yield []

for thing in iterall(
['big', 'medium', 'small'],
['old', 'new'],
['blue', 'green'],
):
print thing

Recursion definitely makes for an elegant solution. However you do take
a bit of a performance hit. If performance matters (and comprehensions
are supposed to be optimized/fast) and you want a "works for N nested
loops solution," then you could build a N deep comprehension on the fly
and eval() it:

Yick...a nice demo of the power of eval, but definitely filed
under the "Hack" heading

I think Martin's solution/recommendation[1] is better
(readability-wise, and "less apt to shoot yourself in the foot
with some bogus generated code"-wise) if you don't mind building
the whole result set in memory which your eval() solution does as
well. I'm curious to see the timing results from adding that
recipe to your test-suite.

The advantage to the recursive-generator solution is that it
should really only keep your initial input and the current result
in memory as the generated item, so you can reasonably iterate
over millions of rows without having gigs of RAM. I don't
believe the recursion will go deeper than the number of lists
you're iterating over, so the stack shouldn't explode.

But as you show, this method comes at a considerable performance
hit. I don't know how much is due to recursion overhead, how
much is due to generator overhead, and how much is due to the
list-building overhead. Perhaps a wiser pythoneer than I will
see something obvious in my code that could be tweaked to reduce
the performance hit.

Ah well. Many solutions to the problem, each with advantages and
disadvantages:

Hard Code the loops (whether using "for" or list-comp):
Pro: easy to code for small sets of data
Pro: easy to understand
Pro: fast
Pro: minimal memory usage
Pro: readily creatable by the python newbie
Con: requires changing code if dimensionality changes
Con: doesn't handle an arbitrary number of lists

Use Martin's cookbook solution:
Pro: popularly documented in the cookbook
Pro: fairly easy to understand
Pro: handles arbitrary numbers of lists
Con: builds all results in-memory
Speed: pro or con?
Notes: generates in minor-order resolution[2]

Recursive-generator solution:
Pro: minimal memory usage
Pro: fairly easy to understand
Con: notably slower
Notes: generates in major-order resolution[2]

Pick whichever meets your needs.

-tkc


[1]
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496807

[2] a term arbitrarily defined/made-up by me as a way to
distinguish whether the results are grouped from
left-to-right/first-to-last (major order) or from
right-to-left/last-to-first (minor order). I happen to like
major order, but that may stem from an undiagnosed neurosis

 

[Reedick, Andrew]

-----Original Message-----

From: Tim Chase [mailto[email protected]]
Sent: Thursday, January 17, 2008 10:30 AM
To: Reedick, Andrew
Cc: breal; (e-mail address removed); (e-mail address removed)
Subject: Re: Creating unique combinations from lists

Yick...a nice demo of the power of eval, but definitely filed
under the "Hack" heading

You hurt my feeling. *sniffle* Given how late python
compiles/evaluates code blocks, I'm thinking that eval() is less hack
and more paradigm ..err.. pythonic. ;-)

I think Martin's solution/recommendation[1] is better
(readability-wise, and "less apt to shoot yourself in the foot
with some bogus generated code"-wise) if you don't mind building
the whole result set in memory which your eval() solution does as
well. I'm curious to see the timing results from adding that
recipe to your test-suite.

Cookbook is relatively decent. 5 deep, 100 iterations:
list comprehension: 11.02
nested for loop : 13.16 +19%
cookbook : 18.85 +71%
recursion : 69.00 +526%
eval : 13.30 +20%

The advantage to the recursive-generator solution is that it
should really only keep your initial input and the current result
in memory as the generated item, so you can reasonably iterate
over millions of rows without having gigs of RAM. I don't
believe the recursion will go deeper than the number of lists
you're iterating over, so the stack shouldn't explode.

Excellent point about memory usage. However, since we're dealing with
exponential algorithms, will you run out of time or memory first?



Here's the test code if anyone wants to play with it. It will let you
specify the levels of nested loops and display the generated code.


Usage: foo.py num_nested_loops num_iterations


import sys
from timeit import Timer

def CreateComprehension(lists):
out = '[' + ','.join(["v%s" % i for i in range(len(lists))]) +
']'
comp = ''.join([ " for v%d in lists[%d]" % (i, i) for i in
range(len(lists))])
return '[ ' + out + comp + ' ]'


num_loops = int(sys.argv[1])
iterations = int(sys.argv[2])

results = []

lists = '''lists = []
for i in range(%d):
lists.append(range(i, i+10))
''' % (num_loops)

print "################################################"
print lists
print

print "################################################"
code = 'r = ' + CreateComprehension(range(num_loops))
t = Timer(code, lists)
results.append("list comprehension: %4.2f" % t.timeit(iterations))
print results[-1:][0]
print code
print


print "################################################"
code = 'r = []\n'
for i in range(num_loops):
code += " " * i
code += "for v%d in lists[%d]:\n" % (i, i)
code += ' ' * num_loops
code += 'r.append(['
code += ','.join( ['v%d' % i for i in range(num_loops)])
code += '])'

t = Timer(code, lists)
results.append("nested for loop : %4.2f" % t.timeit(iterations))
print results[-1:][0]
print code
print


print "################################################"
code = '''r=[[]]
for x in lists:
t = []
for y in x:
for i in r:
t.append(i+[y])
r = t
'''
t = Timer(code, lists)
results.append("cookbook : %4.2f" % t.timeit(iterations))
print results[-1:][0]
print code
print


print "################################################"
code = '''
r = []
def iterall(*iterables):
if iterables:
for head in iterables[0]:
for remainder in iterall(*iterables[1:]):
yield [head] + remainder
else:
yield []

for thing in iterall(%s):
r.append(thing)
''' % ( ','.join([ 'lists[%d]' % i for i in range(num_loops) ]) )

t = Timer(code, lists)
results.append("recursion : %4.2f" % t.timeit(iterations))
print results[-1:][0]
print code
print


print "################################################"
code = '''
def gen(lists):
out = '[' + ','.join(["v%s" % i for i in range(len(lists))]) + ']'
comp = ''.join([ " for v%d in lists[%d]" % (i, i) for i in
range(len(lists))])
return eval('[ ' + out + comp + ' ]')
gen(lists)
'''
t = Timer(code, lists)
results.append("eval : %4.2f" % t.timeit(iterations))
print results[-1:][0]
print code
print

print '\n'.join(results)




*****

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from all computers. GA622

 

[Steven D'Aprano]

-----Original Message-----
From: Tim Chase [mailto[email protected]] Sent: Thursday,
January 17, 2008 10:30 AM To: Reedick, Andrew
Cc: breal; (e-mail address removed); (e-mail address removed) Subject: Re:
Creating unique combinations from lists

Yick...a nice demo of the power of eval, but definitely filed under the
"Hack" heading

You hurt my feeling. *sniffle* Given how late python
compiles/evaluates code blocks, I'm thinking that eval() is less hack
and more paradigm ..err.. pythonic. ;-)

I see your smiley, but even so, do you have any idea how many times eval
is used in the standard library? Not very often.

$ pwd
/usr/lib/python2.5
$ grep -r "eval(.*)" *.py | wc -l
20

Some of those twenty matches are false positives. I manually inspected
them, and by my count there are just ten actual uses of eval:

bdb.py: return eval(expr, globals, locals)
dumbdbm.py: key, pos_and_siz_pair = eval(line)
gettext.py: return eval('lambda n: int(%s)' % plural)
gopherlib.py: _type_to_name_map[eval(name)] = name[2:]
mhlib.py: def do(s): print s; print eval(s)
os.py: eval(name)
pdb.py: x = eval(arg, {}, {})
rexec.py: return eval(code, m.__dict__)
rlcompleter.py: object = eval(expr, self.namespace)
warnings.py: cat = eval(category)


I haven't made any effort to determine how many of them are gaping great
big security holes.