有没有一种方法可以获取“组合组"?在Python上使用itertools的列表不重叠且详尽无遗? [英] Is there a way to get "groups of combinations" of lists that don't overlap, and is exhaustive, using itertools on Python?

问题描述

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

Here's what I mean: if you found all possible 2-element combinations of [1,2,3,4], you would get [1,2], [1,3],[1,4],[2,3],[2,4] and [3,4]

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

What I want is groups of combinations that don't overlap and include all elements. So for example [[1,2],[3,4]] is an example of one "group", because the elements in both combinations do not overlap, and all possible elements are used. [[1,3],[2,4]] is an example of another "group"

顺便说一句，我知道itertools可以让我自己打印组合.因此，例如，以下代码:

By the way, I'm aware that itertools will allow me to print combinations themselves. So for example, the following code:

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)

但是，这只是给我组合.我希望组的组合与元素互斥且穷尽.

But again, that's just giving me combinations. I want GROUPS of combinations that are mutually exclusive and exhaustive with the elements.

此外，我确定我没有使用正确的词汇.如果我要描述的任何东西都有正式的用语，我将不胜感激.

Also, I'm sure I'm not using the proper vocabulary. If there is a formal term for anything I'm describing, I would appreciate learning it.

提前谢谢！

推荐答案

这些组合组"可能称为set partitions into parts of size k.

These "groups of combinations" might be called set partitions into parts of size k.

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

I assume that k is divisor of n, so there are p=n/k parts.

现在，我们可以将零件递归分配.为了避免重复生成同一分区(如01 23 45和01 45 23)，我们应该限制每个组中前导(最小)元素的位置.

Now we can recursively distribute items over parts. To avoid repeated generation of the same partition (like 01 23 45 and 01 45 23), we should restrict places for leading (the smallest) element of every group.

在这里，我将lastfilled参数用于最右边填充部分的索引，因此项目0始终属于第0部分，项目1可能属于部分0或1，但不属于部分2，依此类推.在中间结果为01 __ __的情况下，我们只能在下一级创建01 2_ __，而不是01 __ 2_.

Here I used lastfilled parameter for index of the rightmost filled part, so item 0 always belongs to the 0-th part, item 1 might fall into parts 0 or 1 but not into part 2 and so on. Having intermediate result 01 __ __ we can make only 01 2_ __ at the next level, not 01 __ 2_.

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

Note that number of such partitions is

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

并快速增长(n=9,k=3为280，15/3为1401400). (找到 OEIS序列A060540 )

and grows fast (280 for n=9,k=3, 1401400 for 15/3). (Found OEIS sequence A060540)

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

Python code. I used global lists for parts contents and counts of occupied places in them to save memory, so I have to reset counts to previous state after recursive call.

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的列表不重叠且详尽无遗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！