strange behavior from recursive generator

Phillip Feldman phillip.m.feldman at gmail.com
Fri Sep 23 19:42:13 EDT 2011


I don't know how many times I stared at that code without seeing the error.

Thanks so much!

Phillip

On Fri, Sep 23, 2011 at 1:26 PM, Arnaud Delobelle <arnodel at gmail.com> wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20110923/889925a5/attachment.html>


More information about the Python-list mailing list