recursive algorithm for balls in numbered boxes

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

  1. I've written a recursive class that creates an iterator to solve a general
    formulation of the combinatorics problem known as "balls in numbered boxes"
    (also known as "indistinguishable balls in distinguishable boxes"). The
    code has been extensively tested and appears to work, but isn't terribly
    elegant. Any suggestions about how to improve it will be appreciated.

    Also, I'd like to get this functionality into the Python's `itertools`
    module (the present set of combinatorics functions in `itertools` does not
    include "balls in boxes"). Does anyone know whom I should contact about
    this?

    Phillip

    http://old.nabble.com/file/p32440187/balls_in_numbered_boxes.py
    balls_in_numbered_boxes.py
    --
    View this message in context: http://old.nabble.com/recursive-algorithm-for-balls-in-numbered-boxes-tp32440187p32440187.html
    Sent from the Python - python-list mailing list archive at Nabble.com.
     
    Dr. Phillip M. Feldman, Sep 11, 2011
    #1
    1. Advertising

  2. On Sep 11, 1:43 am, "Dr. Phillip M. Feldman"
    <> wrote:
    > I've written a recursive class that creates an iterator to solve a general
    > formulation of the combinatorics problem known as "balls in numbered boxes"
    > (also known as "indistinguishable balls in distinguishable boxes").  The
    > code has been extensively tested and appears to work, but isn't terribly
    > elegant.  Any suggestions about how to improve it will be appreciated.
    >
    > Also, I'd like to get this functionality into the Python's `itertools`
    > module (the present set of combinatorics functions in `itertools` does not
    > include "balls in boxes").  Does anyone know whom I should contact about
    > this?


    Note that for the version without size limits on individual boxes, the
    itertools.combination function already provides most of what's
    needed. For example:

    import itertools

    def balls_in_boxes(nballs, nboxes):
    n, k = nballs + nboxes - 1, nboxes - 1
    for comb in itertools.combinations(range(n), k):
    yield [y - x - 1 for y, x in zip(comb + (n,), (-1,) +
    comb)]

    print "5 balls in 3 boxes"
    for combination in balls_in_boxes(5, 3):
    print combination
    assert len(combination) == 3
    assert sum(combination) == 5


    This is a well-known trick: to divide 5 (unlabeled) balls amongst 3
    (labeled) boxes, you write down sequences of 5 o's and 2 x's, where
    the o's represent the 5 balls and the 'x's represent dividers:

    ooxooxo -> [2, 2, 1]
    xoooxoo -> [0, 3, 2]

    And 'combinations(7, 2)' yields successively all the possible
    different placements for the 2 dividers in the 7 symbols.


    This question seems to come up often enough (without the box size
    limit twist) that maybe it would be useful to include something like
    this recipe in the itertool documentation.


    For getting this into itertools, I'd suggest opening a feature request
    on bugs.python.org and assigning it to Raymond Hettinger.

    --
    Mark
     
    Mark Dickinson, Sep 11, 2011
    #2
    1. Advertising

  3. Mark Dickinson-2 wrote:
    >
    >
    > This is a well-known trick: to divide 5 (unlabeled) balls amongst 3
    > (labeled) boxes, you write down sequences of 5 o's and 2 x's, where
    > the o's represent the 5 balls and the 'x's represent dividers:
    >
    > ooxooxo -> [2, 2, 1]
    > xoooxoo -> [0, 3, 2]
    >
    > And 'combinations(7, 2)' yields successively all the possible
    > different placements for the 2 dividers in the 7 symbols.
    >
    >
    > This question seems to come up often enough (without the box size
    > limit twist) that maybe it would be useful to include something like
    > this recipe in the itertool documentation.
    >
    >
    > For getting this into itertools, I'd suggest opening a feature request
    > on bugs.python.org and assigning it to Raymond Hettinger.
    >
    > --
    > Mark
    > --
    > http://mail.python.org/mailman/listinfo/python-list
    >
    >


    You are correct--the case without capacity limits can be handled using the
    existing machinery in `itertools`. BTW--That trick with the dividers is
    discussed on page 38 of William Feller's classic text, "An Introduction to
    Probability Theory and Its Applications".

    As per your suggestion, I have opened a feature request and assigned it to
    Raymond. Thanks!
    --
    View this message in context: http://old.nabble.com/recursive-algorithm-for-balls-in-numbered-boxes-tp32440187p32449079.html
    Sent from the Python - python-list mailing list archive at Nabble.com.
     
    Dr. Phillip M. Feldman, Sep 12, 2011
    #3
    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. Xah Lee

    4 balls: lone-ball side-bounce

    Xah Lee, Mar 4, 2006, in forum: Java
    Replies:
    6
    Views:
    529
    Jay Linn
    Mar 6, 2006
  2. Oliver Wong
    Replies:
    1
    Views:
    3,464
  3. Dave Rado
    Replies:
    13
    Views:
    729
    Mark Parnell
    May 11, 2004
  4. AJ
    Replies:
    1
    Views:
    276
    Victor Bazarov
    Dec 11, 2009
  5. Ilmari Heikkinen

    Shiny balls with OpenGL

    Ilmari Heikkinen, Apr 1, 2005, in forum: Ruby
    Replies:
    5
    Views:
    152
    James Adam
    Apr 3, 2005
Loading...

Share This Page