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

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

Re: recursive algorithm for balls in numbered boxes

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

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

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

#13125 — Re: recursive algorithm for balls in numbered boxes

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.

[toc] | [standalone]

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

csiph-web