<p>下面是一种从长度n的集合生成大小为k的所有唯一分区的方法</p>
<p>此类分区的数量为(p为部件数量,等于L):</p>
<pre><code>NPK(n,k) = n! / ((k!)^p * p!)
</code></pre>
<p>生长迅速(n=9时为280,k=3)</p>
<p>算法递归地将项分布在各个部分上。为了避免重复生成相同的分区(如<code>01 23 45</code>和<code>01 45 23</code>),我们应该限制每个组的前导(最小)元素的位置</p>
<p>这里我使用了<code>lastfilled</code>参数作为最右边填充部分的索引,因此项目0始终属于第0部分,项目1可能属于第0部分或第1部分,但不属于第2部分,依此类推。有了中间结果<code>01 __ __</code>,我们只能在下一个级别生成<code>01 2_ __</code>,而不是<code>01 __ 2_</code></p>
<pre><code>def genp(l, parts, cnts, n, k, p, m, lastfilled):
if m == n:
l.append(parts[:])
return
for i in range(min(p, lastfilled + 2)):
if cnts[i] < k:
parts[i][cnts[i]] = m
cnts[i] += 1
genp(l, parts, cnts, n, k, p, m+1, max(i, lastfilled))
cnts[i] -= 1
def genpartssizek(n, k):
l = []
p = n // k
parts = [[0]*k for _ in range(p)]
cnts = [0]*p
genp(l, parts, cnts, n, k, p, 0, -1)
return l
print(genpartssizek(6,2))
[[[0, 1], [2, 3], [4, 5]],
[[0, 1], [2, 4], [3, 5]],
[[0, 1], [2, 5], [3, 4]],
[[0, 2], [1, 3], [4, 5]],
[[0, 2], [1, 4], [3, 5]],
[[0, 2], [1, 5], [3, 4]],
[[0, 3], [1, 2], [4, 5]],
[[0, 4], [1, 2], [3, 5]],
[[0, 5], [1, 2], [3, 4]],
[[0, 3], [1, 4], [2, 5]],
[[0, 3], [1, 5], [2, 4]],
[[0, 4], [1, 3], [2, 5]],
[[0, 5], [1, 3], [2, 4]],
[[0, 4], [1, 5], [2, 3]],
[[0, 5], [1, 4], [2, 3]]]
</code></pre>