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