n distinguishable items into k indistinguishable boxes

Question

Although I have a method for generating the arrangement of n distinct/distinguishable items (from set s) into x boxes (which are not distinguishable), I am wondering if anyone has ideas of something more efficient...or is having to check what is generated just par for the course when doing this sort of combinatorics? e.g. 5 items into 3 boxes:

from sympy.utilities.iterables import cartes, partitions, subsets
from functools import reduce

s = [1,2,3,4,5]
x = 3
for c, p in partitions(len(s), x, size=True): # generates {2:2, 1:1}, {3:1, 1:2}
    if c != x: continue
    args = []
    for k,v in p.items():
        for vi in range(v):
            args.append(subsets(s,k))
    for X in cartes(*args):
        for i in range(1,len(X)):
            if len(X[i]) == len(X[i-1]) and X[i] < X[i-1]: break
        else:
            if len(set(reduce(lambda x,y:x+y, X))) == len(s):
                print(X)

which generates:

((1,), (2,), (3, 4, 5))
((1,), (3,), (2, 4, 5))
((1,), (4,), (2, 3, 5))
((1,), (5,), (2, 3, 4))
((2,), (3,), (1, 4, 5))
((2,), (4,), (1, 3, 5))
((2,), (5,), (1, 3, 4))
((3,), (4,), (1, 2, 5))
((3,), (5,), (1, 2, 4))
((4,), (5,), (1, 2, 3))
((1,), (2, 3), (4, 5))
((1,), (2, 4), (3, 5))
((1,), (2, 5), (3, 4))
((2,), (1, 3), (4, 5))
((2,), (1, 4), (3, 5))
((2,), (1, 5), (3, 4))
((3,), (1, 2), (4, 5))
((3,), (1, 4), (2, 5))
((3,), (1, 5), (2, 4))
((4,), (1, 2), (3, 5))
((4,), (1, 3), (2, 5))
((4,), (1, 5), (2, 3))
((5,), (1, 2), (3, 4))
((5,), (1, 3), (2, 4))
((5,), (1, 4), (2, 3))

To see a simpler results, consider 4 items being put into 2 boxes:

a, bcd
b, acd
c, abd
d, abc
ab, cd
ac, bd
ad, bc

Please state a specific question. (*"I am wondering if anyone has ideas of something more efficient"* is pretty vague) — smci, Nov 21 '19 at 06:45
Just 2 cents: Looks like you also implicitly assume all boxes must contain at least one element, is this really what you need? — Julien, Nov 21 '19 at 07:10
Yes. All boxes should be filled. But like the `partitions` method, perhaps a nice solution would need to check this condition in the generated results. — smichr, Nov 21 '19 at 11:05

score 1 · Accepted Answer · answered Nov 22 '19 at 03:18

1

The efficient implementation is Algorithm U of Knuth's (Vol 4, 3B) that partitions a set into a certain number of blocks. A Python implementation of it is located here.

answered Nov 22 '19 at 03:18

smichr

16,948
2
27
34

score 0 · Answer 2 · answered Nov 21 '19 at 22:36

(This is not an answer, as it only addresses a minor part of the question. But it is too large to fit into a comment ...)

As a variant on this post, here is a funny way to generate only the partitions with a fixed length. Maybe it inspires someone.

def fixed_partitions(n, x, I=1):
    if x <= 1:
        if x == 1:
            yield (n,)
    else:
        for i in range(I, n//2 + 1):
            for p in fixed_partitions(n-i, x-1, i):
                yield (i,) + p

for x in fixed_partitions(7, 3):
    print(x)

> (1, 1, 5)
> (1, 2, 4)
> (1, 3, 3)
> (2, 2, 3)

n distinguishable items into k indistinguishable boxes

2 Answers2