strange behavior from recursive generator

  • Thread starter Dr. Phillip M. Feldman
  • Start date
D

Dr. Phillip M. Feldman

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,480
Members
44,900
Latest member
Nell636132

Latest Threads

Top