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

Groups > comp.lang.python > #13125

Re: recursive algorithm for balls in numbered boxes

Show all headers | View raw

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.

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: recursive algorithm for balls in numbered boxes Peter Otten <__peter__@web.de> - 2011-09-11 14:48 +0200

csiph-web