Place n indistinguishable items into k distinguishable boxes

[Mark Dickinson]

Here's a possible solution.  I'm sure others will comment on how to
fix up its inefficiencies (like the potentially slow string
concatenations...).



def comb(n, k):
    if n == k == 0:
        yield ''
    else:
        if n > 0:
            for x in comb(n-1, k):
                yield ' ' + x
        if k > 0:
            for x in comb(n, k-1):
                yield '|' + x

def boxings(n, k):
    if k == 0:
        if n == 0:
            yield []
    else:
        for s in comb(n, k-1):
            yield map(len, (''.join(s)).split('|'))

for b in boxings(4, 3):
    print b


Output:

[4, 0, 0]
[3, 1, 0]
[3, 0, 1]
[2, 2, 0]
[2, 1, 1]
[2, 0, 2]
[1, 3, 0]
[1, 2, 1]
[1, 1, 2]
[1, 0, 3]
[0, 4, 0]
[0, 3, 1]
[0, 2, 2]
[0, 1, 3]
[0, 0, 4]