recursive algorithm for balls in numbered boxes

Peter Otten __peter__ at web.de
Sun Sep 11 14:48:41 CEST 2011


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.
 

Does the following do what you want?

>>> from itertools import product
>>> def binb(balls, boxsizes):
...     return (fill for fill in product(*[range(bs+1) for bs in boxsizes]) 
if sum(fill) == balls)
...
>>> for item in binb(10, [4, 3, 2, 1, 2]):
...     print item
...
(2, 3, 2, 1, 2)
(3, 2, 2, 1, 2)
(3, 3, 1, 1, 2)
(3, 3, 2, 0, 2)
(3, 3, 2, 1, 1)
(4, 1, 2, 1, 2)
(4, 2, 1, 1, 2)
(4, 2, 2, 0, 2)
(4, 2, 2, 1, 1)
(4, 3, 0, 1, 2)
(4, 3, 1, 0, 2)
(4, 3, 1, 1, 1)
(4, 3, 2, 0, 1)
(4, 3, 2, 1, 0)

If so, your implementation misses a few configurations:

>>> from balls_in_numbered_boxes import balls_in_numbered_boxes as bb
>>> for item in bb(10, [4, 3, 2, 1, 2]):
...     print item
...
[4 3 2 1 0]
[3 3 2 1 1]
[2 3 2 1 2]

> 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?

Basically you have to convince Raymond Hettinger. I recommend that you post 
your suggestion on python-ideas for a general discussion rather than 
approaching him directly.





More information about the Python-list mailing list