strange behavior from recursive generator

Discussion in 'Python' started by Dr. Phillip M. Feldman, Sep 23, 2011.

  1. 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.
     
    Dr. Phillip M. Feldman, Sep 23, 2011
    #1
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. MetalOne
    Replies:
    11
    Views:
    508
    Andrew Koenig
    Dec 21, 2003
  2. Paul Chiusano

    Recursive Generator Question

    Paul Chiusano, Sep 3, 2004, in forum: Python
    Replies:
    8
    Views:
    429
    Brian McErlean
    Sep 3, 2004
  3. aurora
    Replies:
    7
    Views:
    329
    Steven Bethard
    Aug 12, 2005
  4. n00m
    Replies:
    12
    Views:
    1,122
  5. vamsi
    Replies:
    21
    Views:
    2,113
    Keith Thompson
    Mar 9, 2009
Loading...

Share This Page