n个可区分的物品放入k个不可区分的盒子中

Question

虽然我有一种方法可以将 n distinct/distinguishable 项（来自集合 s）排列到 x 个盒子（不可区分）中，但我想知道是否有人有更有效的想法.. .或者在进行这种组合时是否必须检查只为课程生成的内容？例如3 盒 5 件商品：

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)

生成：

((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))

要查看更简单的结果，请考虑将 4 件物品放入 2 个盒子中：

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

Answer 1

（这不是答案，因为它只解决了问题的一小部分。但它太大了，无法放入评论中......）

作为 this post 的变体，这里有一个有趣的方法来只生成固定长度的分区。也许它启发了某人。

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)

Answer 2

高效的实现是 Knuth 的算法 U（第 4 卷，3B），它将一个集合划分为一定数量的块。它的 Python 实现位于 here。

n个可区分的物品放入k个不可区分的盒子中

n distinguishable items into k indistinguishable boxes

python

sympy

combinatorics