generating canonical list of tuples?
Author Message
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,5-a) for c in
range(1,6-a-b) ]

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
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,5-a) for c in
> range(1,6-a-b) ]

> 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
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+2-x1)
#   for x3 in range(1,f+3-x1-x2) ... ]
# 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 = '%s-x%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
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
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
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.

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[index-1] += 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 exec-based version,
and uses about the same amount of memory.

## Jason Orendorff    http://www.jorendorff.com/

Tue, 22 Jun 2004 16:56:24 GMT
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

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 simple-generator, 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
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.

Hire-me-dammit-ly 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

 Page 1 of 1 [ 8 post ]

Relevant Pages