Place n indistinguishable items into k distinguishable boxes

[Arnaud Delobelle]

On Feb 28, 2:40 am, Michael Robertson <mcrobert... at hotmail.com> wrote:
> Hi,
>
> I need a generator which produces all ways to place n indistinguishable
> items into k distinguishable boxes.
>
> For n=4, k=3, there are (4+3-1)!/(3-1)!/4! = 15 ways.
>
> (0,0,4)
[...]

Here is my little function:

---------------
from itertools import chain
from operator import sub

def boxings(n, k):
    """boxings(n, k) -> iterator

    Generate all ways to place n indistiguishable items into k
    distinguishable boxes
    """
    seq = [n] * (k-1)
    while True:
        yield map(sub, chain(seq, [n]), chain([0], seq))
        for i, x in enumerate(seq):
            if x:
                seq[:i+1] = [x-1] * (i+1)
                break
        else:
            return
---------------

It is purely iterative.  I think it is not too wasteful but I haven't
tried to optimise it in any way.

In the function, 'seq' iterates over all increasing sequences of
length k-1 over {0,1,..n}.

Example:

>>> for b in boxings(4, 3): print b
...
[4, 0, 0]
[3, 1, 0]
[2, 2, 0]
[1, 3, 0]
[0, 4, 0]
[3, 0, 1]
[2, 1, 1]
[1, 2, 1]
[0, 3, 1]
[2, 0, 2]
[1, 1, 2]
[0, 2, 2]
[1, 0, 3]
[0, 1, 3]
[0, 0, 4]

... here is another attempt on the same principle:

---------------
def boxings(n, k):
    """boxings(n, k) -> iterator

    Generate all ways to place n indistiguishable items into k
    distinguishable boxes
    """
    seq = [n]*k + [0]
    while True:
        yield tuple(seq[i] - seq[i+1] for i in xrange(k))
        i = seq.index(0) - 1
        if i >= 1:
            seq[i:k] = [seq[i] - 1] * (k - i)
        else:
            return

--
Arnaud