Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Peter Otten <__peter__@web.de>
Subject: Re: recursive algorithm for balls in numbered boxes
Date: Sun, 11 Sep 2011 14:48:41 +0200
Organization: None
References: <32440187.post@talk.nabble.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 7Bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.986.1315745317.27778.python-list@python.org>
Lines: 55
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:13125

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.