Improve this recursive code please!

[Sean Ross]

Hi.

I've been thinking about this problem for several days. Unfortunately, I
haven't found a solution for you, but I have found the form of a solution
that perhaps someone else here will know how to implement:

for arrangement in xuniquepermute(xdistribute(items, bins)):
    print arrangement  # or perform some other operations with this
arrangement

xdistribute(items, bins) would be a generator function that returns, one by
one, the ways to distribute items in bins, and xuniquepermute() would
return, one by one, the unique permutations for each distribution.

I have a version of distribute that does not do what I want, but does show
what I mean when I say that it shows "the ways to distribute items in bins".
Preferably, this could be changed into a generator function, and perhaps one
that is iterative, to avoid the maximum recursion depth issue.

# credit: based on Java version by Dr. Jason Morrison
def distribute(items, bins):
    def __distribute(accum, maxvalue, subtotal, spots):
        remaining = items - subtotal
        if spots == 1:
            print accum + [remaining]
        else:
            smallest, remainder = divmod(remaining, spots)
            if remainder:
                smallest += 1
            for i in xrange(maxvalue, smallest-1, -1):
                __distribute(accum + [i], min(i,remaining-i),
                             subtotal + i, spots-1)

    __distribute([],items,0,bins)

distribute(items=5, bins=3)


# this outputs
[5, 0, 0]
[4, 1, 0]
[3, 2, 0]
[3, 1, 1]
[2, 2, 1]

Once you have this, you'd need to use xuniquepermute() to generate things
like, for instance,

[5, 0, 0], [0, 5, 0], [0, 0, 5]

since it's a different arrangement when the items are packed into a
different bin. An xpermute() function exists, but this will not generate the
information you need as it will return

[5, 0, 0], [5, 0, 0], [0, 5, 0], [0, 0, 5], [0, 5, 0], [0, 0, 5]

I haven't been able to implement either xdistribute() or xuniquepermute()
myself, although I will keep trying because I think the idea is sound and
would work as a solution to your problem. I would be relieved to see an
implementation of this, as it's become something of an itch for me.

Sorry I couldn't be of more assistance,
Sean


"waxmop" <waxmop at sarcastic-horse.com> wrote in message
news:3EB7DF65.55A50CD4 at sarcastic-horse.com...
> Hi - I wrote a program that gets two arguments: numbricks, and numbins.
> The program calculates every possible way to distribute all the bricks
> into the bins, using a recursive function.
>
> The program works ok, especially when numbricks and numbins are under 5
> each.  However, I need to run this program when numbricks = 100 or more,
> and I'm concerned about memory issues.
>
> Is there a way I can avoid building a giant stack?  This program doesn't
> need to run fast at all.  It just needs to run with enormous numbers of
> bricks and bins, even if it takes a few hours.  I just don't want to
> overload our server while it's happening.
>
> Finally. I do have access to a beowulf cluster; is this something that
> could take advantage of that?
>
> I'm still learning python, so other comments about the code are
> welcomed.  And no, this isn't a homework assignment.
>
> The program can be run like so:
>
> ./tupp.py 4 4
>
> or
>
> ./tupp.py -help
>
> to get a usage message.
>
>
> Here's the program:
>
> #! /usr/bin/env python
>
> import sys
> import types
> import string
>
> def mk_tree(numbricks, numbins):
>   bin = [0]*numbins
>   results = {}
>   mk_tree_r(numbricks, numbins, bin, results)
>   tups = results.keys()
>   tups.sort()
>   tups.reverse()
>   return tups
>
>
> def mk_tree_r(numbricks, numbins, bin, results):
>   if countbricks(bin) < numbricks:
>     for i in range(numbins):
>       bin[i] += 1
>       mk_tree_r(numbricks, numbins, bin, results)
>       bin[i] -= 1
>   else:
>     t = tuple(bin)
>     results[t] = 1
>
>
> def countbricks(bin):
>   sum = 0
>   for bricks in bin:
>     if bricks:
>       sum += bricks
>   return sum
>
>
> #main method:
> def main():
>
>   usage = """
>       USAGE: python %s <number of bricks> <number of bins>
>         <number of bricks> must be an integer.
>         <number of bins> must also be an integer.
>     """ % sys.argv[0]
>
>   try:
>     numbricks = string.atoi(sys.argv[1])
>     if type(numbricks) is not types.IntType: raise
>     numbins = string.atoi(sys.argv[2])
>     if type(numbins) is not types.IntType: raise
>   except:
>     raise SystemExit, usage
>
>   t = mk_tree(numbricks, numbins)
>   f = open('tuples.txt', 'w')
>   for tup in t:
>     print >> f, tup
>   f.close()
>   print "wrote a total of %d tuples to tuples.txt" % len(t)
>
> if __name__ == '__main__': main()
>
>
>