strange behavior from recursive generator

Dr. Phillip M. Feldman Phillip.M.Feldman at gmail.com
Fri Sep 23 22:09:32 CEST 2011


A few weeks ago, I wrote a class that creates an iterator for solving the
general unlabeled-balls-in-labeled boxes occupancy problem. Chris Rebert
converted my code to a generator, which made the code cleaner, and I
subsequently simplified it somewhat further.

My problem is the following: All of these versions of the code work fine for
very small problems, but do not produce the full set of occupancy
distributions for larger problems. The following sample input and output
show what happens with two balls and two boxes (to keep things simple, I've
made the boxes large enough so that each box can hold both balls).

In [6]: x= balls_in_labeled_boxes(2,[2,2])

In [7]: list(x)
balls=2, box_sizes=[2, 2]
About to make recursive call.  balls_in_other_boxes=0, box_sizes=[2]
i=0, distribution_other=(0,)
About to make recursive call.  balls_in_other_boxes=1, box_sizes=[2]
i=0, distribution_other=(1,)
About to make recursive call.  balls_in_other_boxes=2, box_sizes=[2]
i=0, distribution_other=(2,)
Out[7]: [(2, 0), (1, 1), (0, 2)]

Note that Out[7] above gives the correct result, showing all three possible
distributions. Now lets try the same thing with three boxes.

In [8]: x= balls_in_labeled_boxes(2,[2,2,2])

In [9]: list(x)
balls=2, box_sizes=[2, 2, 2]
About to make recursive call.  balls_in_other_boxes=0, box_sizes=[2, 2]
i=0, distribution_other=(0, 0)
About to make recursive call.  balls_in_other_boxes=1, box_sizes=[2, 2]
i=0, distribution_other=(1, 0)
About to make recursive call.  balls_in_other_boxes=2, box_sizes=[2, 2]
i=0, distribution_other=(2, 0)
i=1, distribution_other=(1, 1)
Out[9]: [(2, 0, 0), (1, 1, 0), (0, 2, 0), (0, 1, 1)]

When there are no balls in the initial box, the recursive call should
produce the same three occupancy distributions that we saw above, but one of
them is now missing. If someone can shed light on why this is happening, I'd
be grateful.

Phillip

http://old.nabble.com/file/p32503886/balls_in_labeled_boxes.py
balls_in_labeled_boxes.py 
-- 
View this message in context: http://old.nabble.com/strange-behavior-from-recursive-generator-tp32503886p32503886.html
Sent from the Python - python-list mailing list archive at Nabble.com.




More information about the Python-list mailing list