有没有办法在 Python 上使用 itertools 获取 "groups of combinations" 不重叠且详尽无遗的列表？

Question

我的意思是：如果您找到 [1,2,3,4] 的所有可能的 2 元素组合，您将得到 [1,2]、[1,3]、[1,4] ,[2,3],[2,4] 和 [3,4]

我想要的是不重叠且包含所有元素的组合组。因此，例如 [[1,2],[3,4]] 是一个“组”的示例，因为两个组合中的元素不重叠，并且使用了所有可能的元素。 [[1,3],[2,4]] 是另一个“组”的例子

顺便说一句，我知道 itertools 将允许我自己打印组合。例如，下面的代码：

combinations = itertools.combinations([1,2,3,4], 2)
for c in combinations:
    print(c)

将输出：

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

但同样，这只是给我组合。我想要 GROUPS 的组合，这些组合与元素互斥且详尽无遗。

此外，我确定我没有使用正确的词汇。如果我描述的任何内容有正式术语，我将不胜感激。

提前致谢！

Answer 1

这些“组合组”可能被称为set partitions into parts of size k。

我假设 k 是 n 的约数，所以有 p=n/k 个部分。

现在我们可以递归地将项目分布到各个部分。为了避免重复生成相同的分区（如 01 23 45 和 01 45 23），我们应该限制每个组的前导（最小）元素的位置。

这里我使用了lastfilled参数作为最右边填充部分的索引，所以项目0总是属于第0部分，项目1可能属于第0部分或第1部分但不属于第2部分等等在。有了中间结果01 __ __，我们只能在下一级做出01 2_ __，而不是01 __ 2_。

请注意，此类分区的数量为

NPK(n,k) = n! / ((k!)^p * p!)

并快速增长（280 代表 n=9,k=3，1401400 代表 15/3）。（找到 OEIS sequence A060540）

Python 代码。我使用了零件内容的全局列表和其中占用的位置计数以节省内存，所以我必须在递归调用后将计数重置为以前的状态。

n = 6
k = 2
p = n // k
parts = [[0]*k for _ in range(p)]
cnts = [0]*p

def genparts(m, lastfilled):
    if m == n:
        print(parts)
        return
    for i in range(min(p, lastfilled + 2)):
        if cnts[i] < k:
            parts[i][cnts[i]] = m
            cnts[i] += 1
            genparts(m+1, max(i, lastfilled))
            cnts[i] -= 1

genparts(0, -1)

[[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]]

有没有办法在 Python 上使用 itertools 获取 "groups of combinations" 不重叠且详尽无遗的列表？

Is there a way to get "groups of combinations" of lists that don't overlap, and is exhaustive, using itertools on Python?

python

algorithm

math

discrete-mathematics