RE: Creating unique combinations from lists
-Original Message-
From: [EMAIL PROTECTED] [mailto:python-
[EMAIL PROTECTED] On Behalf Of Tim Chase
Sent: Wednesday, January 16, 2008 3:40 PM
To: breal
Cc: python-list@python.org
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
--
http://mail.python.org/mailman/listinfo/python-list
RE: Creating unique combinations from lists
-Original Message-
From: Tim Chase [mailto:[EMAIL PROTECTED]
Sent: Thursday, January 17, 2008 10:30 AM
To: Reedick, Andrew
Cc: breal; python-list@python.org; [EMAIL PROTECTED]
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
--
http://mail.python.org/mailman/listinfo/python-list
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: 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 ;) -- http://mail.python.org/mailman/listinfo/python-list
Re: Creating unique combinations from lists
On Thu, 17 Jan 2008 10:44:51 -0600, Reedick, Andrew wrote:
-Original Message-
From: Tim Chase [mailto:[EMAIL PROTECTED] Sent: Thursday,
January 17, 2008 10:30 AM To: Reedick, Andrew
Cc: breal; python-list@python.org; [EMAIL PROTECTED] 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.
--
Steven
--
http://mail.python.org/mailman/listinfo/python-list
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://mail.python.org/mailman/listinfo/python-list
RE: Creating unique combinations from lists
-Original Message- From: [EMAIL PROTECTED] [mailto:python- [EMAIL PROTECTED] On Behalf Of breal Sent: Wednesday, January 16, 2008 2:15 PM To: python-list@python.org 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/ -- http://mail.python.org/mailman/listinfo/python-list
Re: Creating unique combinations from lists
On Jan 16, 11:33 am, Reedick, Andrew [EMAIL PROTECTED] wrote: -Original Message- From: [EMAIL PROTECTED] [mailto:python- [EMAIL PROTECTED] On Behalf Of breal Sent: Wednesday, January 16, 2008 2:15 PM To: [EMAIL PROTECTED] 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! -- http://mail.python.org/mailman/listinfo/python-list
Re: Creating unique combinations from lists
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Creating unique combinations from lists
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Creating unique combinations from lists
On Jan 16, 11:15 am, breal [EMAIL PROTECTED] wrote: 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Creating unique combinations from lists
On Wed, 16 Jan 2008 11:15:16 -0800, breal wrote: 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? -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: Creating unique combinations from lists
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? 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Creating unique combinations from lists
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... -- http://mail.python.org/mailman/listinfo/python-list
Re: Creating unique combinations from lists
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... 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Creating unique combinations from lists
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 -- http://mail.python.org/mailman/listinfo/python-list
