Home Original page

Improve this recursive code please!

Anton Vredegoor anton at vredegoor.doge.nl
Sun May 11 06:59:54 EDT 2003 
Steven Taschuk <staschuk at telusplanet.net> wrote:

[posts nice successor function]

>distinct but all bricks the same; it produces results in sorted
>order; it holds only one result in memory at a time, avoiding a

No, it doesn't produce the results in sorted order, not even in
reverse sorted order :-)

This one does:

def arrangements(number_of_bricks, number_of_bins):
    """generate arrangements of m bricks in n bins"""
    stack = number_of_bricks
    bins = [0]*number_of_bins
    if not bins : return
    first, last = 0, number_of_bins-1
    # take all bricks from the stack and put them in the last bin
    bins[last], stack =  bins[last]+stack, 0
    yield tuple(bins)
    # while not all bricks are in the first bin
    while bins[first] < number_of_bricks:
        # find the donor bin with the highest index
        donor = last
        while bins[donor] is 0 and donor > first:   donor -= 1 
        # if there are empty bins with an index higher than donor, 
        # find the empty bin with the highest index, else use donor
        higher = last
        while bins[higher] is not 0 and higher > donor:  higher -= 1 
        # take all bricks from the donor bin and add them to the
        # stack
        stack, bins[donor] = stack+bins[donor], 0
        # take one brick from the stack and add it to the bin to 
        # the left of the donor bin
        stack, bins[donor-1] = stack-1, bins[donor-1]+1
        # take the rest of the bricks from the stack and add them
        # to the higher bin 
        bins[higher], stack = bins[higher]+stack, 0
        yield tuple(bins)

def test():
    for i,x in enumerate(arrangements(4,4)):
        print "%2s %s" %(i,x)
        
if __name__=='__main__':
    test()

One question that remains is: Do we have enough mathematicians in this
group to count the number of arrangements that are produced this way?

:-> 

Anton
More information about the Python-list mailing list