generating canonical list of tuples?

[Joshua Muskovitz]

> 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! =-----