strange behavior from recursive generator

Arnaud Delobelle arnodel at gmail.com
Fri Sep 23 22:26:13 CEST 2011


On 23 September 2011 21:09, Dr. Phillip M. Feldman
<Phillip.M.Feldman at gmail.com> wrote:
>
> 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.

Line 46:

         for distribution_other in _balls_in_unlabeled_boxes(

Should be:


         for distribution_other in _balls_in_labeled_boxes(

HTH

-- 
Arnaud



More information about the Python-list mailing list