generating canonical list of tuples?
Author 
Message 
Joshua Muskovit #1 / 8

generating canonical list of tuples?
Here's what I'm trying to do... create "magicFunction(limit, dimension)" to return a list of tuples. Each tuple contains exactly "dimension" elements, all positive integers. The sum of these elements must be less than or equal to "limit". for example, magicFunction(5,3) should return: [ (1,1,1), (1,1,2), (1,1,3), (1,2,1), (1,2,2), (1,3,1), (2,1,1), (2,1,2), (2,2,1), (3,1,1) ] The order of the resulting tuples is unimportant. If "dimension" is a fixed number, this is easy. In the case where dimension is 3, this can be written as: [ (a,b,c) for a in range(1,4) for b in range (1,5a) for c in range(1,6ab) ] But (and here is the REAL question)... how does one do this when dimension is a variable? Option 1: Recursion. Recursion will cause a memory explosion when the limit and dimension begin to grow, and so this isn't a good solution. Option 2: Exec. Construct a line of python code dynamically based on the above example, and exec it. Would this be considered a good solution? Option 3: ??? Is there a pythonic way of doing this?  josh = Posted via Newsfeeds.Com, Uncensored Usenet News = http://www.***.com/  The #1 Newsgroup Service in the World! == Over 80,000 Newsgroups  16 Different Servers! =

Tue, 22 Jun 2004 05:28:05 GMT 


Steve Holde #2 / 8

generating canonical list of tuples?
Quote: > Here's what I'm trying to do... > create "magicFunction(limit, dimension)" to return a list of tuples. Each > tuple contains exactly "dimension" elements, all positive integers. The sum > of these elements must be less than or equal to "limit". > for example, magicFunction(5,3) should return: > [ (1,1,1), (1,1,2), (1,1,3), (1,2,1), (1,2,2), (1,3,1), (2,1,1), (2,1,2), > (2,2,1), (3,1,1) ] > The order of the resulting tuples is unimportant. > If "dimension" is a fixed number, this is easy. In the case where dimension > is 3, this can be written as: > [ (a,b,c) for a in range(1,4) for b in range (1,5a) for c in > range(1,6ab) ] > But (and here is the REAL question)... how does one do this when dimension > is a variable? > Option 1: Recursion. Recursion will cause a memory explosion when the > limit and dimension begin to grow, and so this isn't a good solution.
I don't see why you make this assertion. Surely an exhaustive search for dimension 32 could be performed with no more than 33 active calls. Of course the space required to store the list will increase as limit increases, but since you want to return the list that's a given anyway. Quote: > Option 2: Exec. Construct a line of python code dynamically based on the > above example, and exec it. Would this be considered a good solution?
Perhpas by some, but my own feeling is that exec (and to a lesser extent eval(), which might be another choice for this problem) should be reserved as an absolute last resort. Quote: > Option 3: ???
I note that you regard (1,1,2) as different from (1,2,1) and (2,1,1), so ordering is clearly important. This makes it quite a knotty problem. Quote: > Is there a pythonic way of doing this?
Go for recursion! regards Steve  http://www.holdenweb.com/

Tue, 22 Jun 2004 05:43:32 GMT 


Joshua Muskovit #3 / 8

generating canonical list of tuples?
Quote: > Option 1: Recursion. Recursion will cause a memory explosion when the > limit and dimension begin to grow, and so this isn't a good solution. > Option 2: Exec. Construct a line of python code dynamically based on the > above example, and exec it. Would this be considered a good solution? > Option 3: ???
Ok, so I've tried a function which brute force cranks out the tuples by adding one to the last element, carrying it over, etc. And I wrote the exec method. And I wrote the recursion method. The exec runs at least six times faster than the brute force method. Recursion causes memory to dump even sooner, since there are tons of redundant lists to gc. The code for the exec method is as follows: def genWhiteTuples(total, blocks): # produce the set of all tuples with "blocks" elements, where # the sum of the elements is less than or equal to "total" # for example, genWhiteTuples(5,3) returns # [ (1,1,1), (1,1,2), (1,1,3), (1,2,1), (1,2,2), # (1,3,1), (2,1,1), (2,1,2), (2,2,1), (3,1,1) ] # create an evil list comprehension to compute... # [ (x1,x2,x3,...) for x1 in range(1,f+1) for x2 in range(1,f+2x1) # for x3 in range(1,f+3x1x2) ... ] # where f is the max value of the first element of the tuple f = total  blocks + 1 sub = '' elements = [] clauses = [] for i in range(1, blocks + 1): elements.append('x%d' % i) clauses.append('for x%d in range(1, f+%d%s)' % (i,i,sub) ) sub = '%sx%d' % (sub, i) if len(elements) == 1: tup = '(%s,)' % elements[0] else: tup = '(' + ','.join(elements) + ')' cmd = 'good = [ %s %s ]' % (tup, ' '.join(clauses) ) exec(cmd) return good This is pretty cool, but also pretty unmaintainable. Is there a better solution? By the way, trying to compute genWhiteTuples(39, 6) caused my machine to run out of paging space after burning about 500MB. :) I'm still working on a better algorithm than this, since even with making this run better, it'll still consume the same RAM.  j = Posted via Newsfeeds.Com, Uncensored Usenet News = http://www.newsfeeds.com  The #1 Newsgroup Service in the World! == Over 80,000 Newsgroups  16 Different Servers! =

Tue, 22 Jun 2004 15:24:19 GMT 


Paul Rubi #4 / 8

generating canonical list of tuples?
Quote:
> Option 1: Recursion. Recursion will cause a memory explosion when the > limit and dimension begin to grow, and so this isn't a good solution.
There will be a memory explosion as the limit and dimension grow whether you use recursion or not, because the size of the output list will grow very rapidly.

Tue, 22 Jun 2004 16:06:51 GMT 


Joshua Muskovit #5 / 8

generating canonical list of tuples?
Quote: > There will be a memory explosion as the limit and dimension grow > whether you use recursion or not, because the size of the output list > will grow very rapidly.
Yes, this occurred to me  that regardless of algorithm, the resulting data is identical, and expands very quickly as the dimension grows. I'm working on solving that issue separately from optimizing this mechanism. I'm also trying to understand some of the subtleties of Python 2.x and this is a good way to ferret some of them out.  j = Posted via Newsfeeds.Com, Uncensored Usenet News = http://www.newsfeeds.com  The #1 Newsgroup Service in the World! == Over 80,000 Newsgroups  16 Different Servers! =

Tue, 22 Jun 2004 16:48:11 GMT 


Jason Orendorf #6 / 8

generating canonical list of tuples?
Quote: > Ok, so I've tried a function which brute force cranks out the tuples by > adding one to the last element, carrying it over, etc. And I > wrote the exec method. And I wrote the recursion method. The exec > runs at least six times faster than the brute force method.
I haven't been following this thread; perhaps someone already suggested using a generator for this. # Python 2.2 only from __future__ import generators def genWhiteTuples(total, blocks): """ The 'brute force' method, as a generator. """ if total < blocks: # Trivial case return result = [1] * blocks running_total = blocks while 1: yield tuple(result) while running_total < total: # Easy. Just increment the rightmost number. result[1] += 1 running_total += 1 yield tuple(result) # Look for an element to reset. index = blocks  1 while index > 0: if result[index] > 1: # We found an element to reset. # (Must also increment the element to its left.) running_total = running_total  result[index] + 2 result[index] = 1 result[index1] += 1 break index = 1 else: # This means we're done. return You can use a generator in a for statement, just as you would use a list. for x1, x2, x3 in genWhiteTuples(10, 3): do_something(x1, x2, x3) In this case, RAM consumption is low, because the tuples are generated one at a time, as needed, instead of generating them all at once and putting them in a list. In fact, I can even: n = 0 for t in genWhiteTuples(39, 6): n += 1 # count how many results print n It runs in about 10 seconds on my machine, and doesn't use much RAM. The result is 3262623. If you *must* have a list, the syntax is pretty simple: L = list(genWhiteTuples(20, 10)) On my machine, this runs about as fast as your execbased version, and uses about the same amount of memory. ## Jason Orendorff http://www.jorendorff.com/

Tue, 22 Jun 2004 16:56:24 GMT 


Alex Martell #7 / 8

generating canonical list of tuples?
Quote: > Here's what I'm trying to do... > create "magicFunction(limit, dimension)" to return a list of tuples. Each > tuple contains exactly "dimension" elements, all positive integers. The sum > of these elements must be less than or equal to "limit". > for example, magicFunction(5,3) should return: > [ (1,1,1), (1,1,2), (1,1,3), (1,2,1), (1,2,2), (1,3,1), (2,1,1), (2,1,2), > (2,2,1), (3,1,1) ] > The order of the resulting tuples is unimportant.
OK, quite clear. Quote: > If "dimension" is a fixed number, this is easy. In the case where
dimension ... Quote: > But (and here is the REAL question)... how does one do this when dimension > is a variable?
Think "counting in a variable base"  it's often a good mindset in such 'enumeration problems'. In counting we increment each digit as far as possible, then when the digit would overflow we reset it to the minimum value and proceed to the next most significant digit. Here, a 'digit overflows' when the total reaches the limit, so...: def magicFunction(limit, dimension): if limit < dimension: return [] current = [1]*dimension results = [tuple(current)] def total(current): import operator return reduce(operator.add, current) while 1: index = 0 while index < dimension: if total(current) < limit: current[index] += 1 results.append(tuple(current)) break # exit inner loop, continue outer loop elif current[index] > 1: current[index] = 1 index += 1 else: return results Rather than recomputing the total() each time, you could also maintain it incrementally. This also looks like a good candidate to make into a simplegenerator, by just changing the .append (and the first assiment to results) into yield statements and making the return statements expressionless  but that, obviously, wouldn't change the algorithm, just package it up in a potentially more usable way. Alex

Tue, 22 Jun 2004 22:02:19 GMT 


Joshua Muskovit #8 / 8

generating canonical list of tuples?
Yes, as Alex and Jason both correctly point out, the concept I was missing is that of using a generator. This was something I read about in the new docs, but didn't fully grok. This is an excellent example of how and why to use them. In retrospect, the use of the word "generating" in my subject line should have tipped me off! :) I'm hoping to give this idea a spin later today! Thanks for all the help. Hiremedammitly yrs,  josh = Posted via Newsfeeds.Com, Uncensored Usenet News = http://www.newsfeeds.com  The #1 Newsgroup Service in the World! == Over 80,000 Newsgroups  16 Different Servers! =

Wed, 23 Jun 2004 00:58:07 GMT 


