Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #13094 > unrolled thread

recursive algorithm for balls in numbered boxes

Back to article view | Back to comp.lang.python

Contents

  recursive algorithm for balls in numbered boxes "Dr. Phillip M. Feldman" <Phillip.M.Feldman@gmail.com> - 2011-09-10 17:43 -0700
    Re: recursive algorithm for balls in numbered boxes Mark Dickinson <mdickinson@enthought.com> - 2011-09-11 08:08 -0700
      Re: recursive algorithm for balls in numbered boxes "Dr. Phillip M. Feldman" <Phillip.M.Feldman@gmail.com> - 2011-09-12 08:47 -0700

#13094 — recursive algorithm for balls in numbered boxes

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.

[toc] | [next] | [standalone]

#13129

On Sep 11, 1:43 am, "Dr. Phillip M. Feldman"
<Phillip.M.Feld...@gmail.com> 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

[toc] | [prev] | [next] | [standalone]

#13187

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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web