Python中的集合划分

Question

我有一个数组 [1,2,3]

我想使用数组中的所有元素生成所有可能的组合：

结果：

[[1], [2], [3]]
[[1,2], [3]]
[[1], [2,3]]
[[1,3], [2]]
[[1,2,3]]

- user2880257

---

https://dev59.com/QnRB5IYBdhLWcg3w7riV?rq=1 - Maciej Gol

对于 [1,2,3,4]，您预期会得到什么结果？ - Tim Pietzcker

你实际上正在寻找“集合划分”（set partitions）的概念。 - poke

这不是重复的问题。链接的问题有答案返回列表，但不包含原始集合中的所有元素。这个问题是不同的。事实上，另一个问题甚至没有那么密切相关。 - rlms

我同意，这个问题不是重复的（无论如何，它可能会有另一个潜伏的问题）。 "itertools.combinations" 不会产生集合划分。 - DSM

Answer 1

鉴于这道好问题又被提起来了，这里是一个新的答案。

这个问题可以递归地解决：如果您已经有一个由n-1个元素组成的分区，如何使用它来划分n个元素？将第n个元素放置在现有子集中的一个中，或将其添加为新的单例子集。就是这样；没有itertools，没有集合，没有重复输出，总共只需要进行n次partition()调用：

def partition(collection):
    if len(collection) == 1:
        yield [ collection ]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        # put `first` in its own subset 
        yield [ [ first ] ] + smaller


something = list(range(1,5))

for n, p in enumerate(partition(something), 1):
    print(n, sorted(p))

输出：

1 [[1, 2, 3, 4]]
2 [[1], [2, 3, 4]]
3 [[1, 2], [3, 4]]
4 [[1, 3, 4], [2]]
5 [[1], [2], [3, 4]]
6 [[1, 2, 3], [4]]
7 [[1, 4], [2, 3]]
8 [[1], [2, 3], [4]]
9 [[1, 3], [2, 4]]
10 [[1, 2, 4], [3]]
11 [[1], [2, 4], [3]]
12 [[1, 2], [3], [4]]
13 [[1, 3], [2], [4]]
14 [[1, 4], [2], [3]]
15 [[1], [2], [3], [4]]

- alexis

---

我猜这个解决方案比我想象的更明显 :-)（在新问题中发布了相同的内容，使此问题重新浮现） - Stefan Pochmann

这个算法是由谁提出的？ - étale-cohomology

@étale-cohomology，这是我自己想出来的。我相信我不是第一个这样做的人。 - alexis

有没有办法将结果限制为严格连续的列表？例如，我想删除结果[[1, 3, 4], [2]]，[[1, 4], [2, 3]]等。此外，是否有一种方法可以限制分区数？例如，假设我将分区数限制为3，我希望算法删除最后一个集合[[1]，[2]，[3]，[4]]，因为它有4个分区。我在以下链接中提出了一个问题：https://stackoverflow.com/questions/45820190/set-ordered-partitions-in-python-of-maximum-size-n - Eric B

我怀疑相同的方法可以奏效，但这是一个不同的问题；我建议您精确地阐述它并提出一个新问题（可以引用此问题，明确说明这不是同一个问题）。 - alexis

Answer 2

与我的评论所示不同，我无法快速找到一个基于itertools的相对快速的解决方案！编辑：这不再完全正确，我有一个相当简短的（但是慢而难以阅读）使用大量itertools的解决方案，请参见答案末尾。这就是我得到的：

思路是找到将整数相加得到列表长度的所有组合，然后获取长度的切片列表。

例如，对于长度为3的列表，组合或分区为(3)、(2, 1)、(1, 2)和(1, 1, 1)。因此，我们返回列表的前3项；前2项，然后是下一项；第1项，然后是下2项；第1项，然后是下1项，然后是下1项。

我从这里获得了用于整数分区的代码。但是，分区函数不会返回分区的所有排列（即对于3，它只会返回(3)、(2, 1)和(1, 1, 1)）。因此，我们需要在每个分区上调用itertools.permutations。然后，我们需要删除重复项——就像permutations([1, 2, 3])是[[1, 2, 3]，[1, 3, 2]，[2, 1, 3]，[2, 3, 1]，[3, 1, 2]，[3, 2, 1]]；permutations([1, 1, 1])是[[1, 1, 1]，[1, 1, 1]，[1, 1, 1]，[1, 1, 1]，[1, 1, 1]，[1, 1, 1]]。一个简单的方法是将每个元组列表转换为set以删除重复项。

然后，唯一剩下的就是获取长度元组中的列表切片。 例如，f([1, 2, 3], [0, 0, 1, 2, 1, 0]) 转化为 [[0], [0, 1], [2, 1, 0]]。

我的定义如下：

def slice_by_lengths(lengths, the_list):
    for length in lengths:
        new = []
        for i in range(length):
            new.append(the_list.pop(0))
        yield new

现在我们只需要将所有内容结合起来：

def subgrups(my_list):
    partitions = partition(len(my_list))
    permed = []
    for each_partition in partitions:
        permed.append(set(itertools.permutations(each_partition, len(each_partition))))

    for each_tuple in itertools.chain(*permed):
        yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))

>>> for i in subgrups(my_list):
        print(i)

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]

此外，还需要在程序开头执行import itertools和from copy import deepcopy。

编辑：您提供的输出不清晰。 我假设您想要我给出的函数，但是您的输出也包含[[1,3]，[2]]，其中输出中的元素顺序不同，不像您建议的其余部分（我冒昧假设您实际想要的是 [[1, 2]，[3]] 而不是 [[1, 2]，3] ）。

也就是说，我认为您想要作为输出的内容是这样的：

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]

实际情况是这样的：

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]
[[1], [3], [2]]
[[1], [3, 2]]
[[1, 3], [2]]
[[1, 3, 2]]
[[2], [1], [3]]
[[2], [1, 3]]
[[2, 1], [3]]
[[2, 1, 3]]
[[2], [3], [1]]
[[2], [3, 1]]
[[2, 3], [1]]
[[2, 3, 1]]
[[3], [1], [2]]
[[3], [1, 2]]
[[3, 1], [2]]
[[3, 1, 2]]
[[3], [2], [1]]
[[3], [2, 1]]
[[3, 2], [1]]
[[3, 2, 1]]

然后，您只需要针对原始列表的每个3个元素长度的排列调用subgroups，例如在 itertools.permutations(my_list, len(my_list)) 中的每个排列中。

编辑：现在为了实现我承诺的基于短的itertools的解决方案。警告-它可能既难以阅读又缓慢。

首先，我们用以下内容替换slice_by_lengths：

def sbl(lengths, the_list):
    for index, length in enumerate(lengths):
        total_so_far = sum(lengths[:index])
        yield the_list[total_so_far:total_so_far+length]

然后从这个答案中，我们获取了整数分配函数：

def partition(number):
    return {(x,) + y for x in range(1, number) for y in partition(number-x)} | {(number,)}

这个函数实际上为我们获取所有整数划分的排列，因此我们不需要

for each_partition in partitions:
    permed.append(set(itertools.permutations(each_partition, len(each_partition))))

然而，我们现在使用的方法是递归的，并且我们正在使用Python实现它，因此比以前的方法要慢得多。

然后我们只需要将它们组合起来：

def subgrups(my_list):
    for each_tuple in partition(len(my_list)):
        yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))

或者不太易读，但没有函数定义：

def subgrups(my_list):
    for each_tuple in (lambda p, f=lambda n, g:
                          {(x,) + y for x in range(1, n) for y in g(n-x, g)} | {(n,)}:
                              f(p, f))(len(my_list)):
        yield list(my_list[sum(each_tuple[:index]):sum(each_tuple[:index])+length] for index, length in enumerate(each_tuple))

这是一个函数定义和两行代码，与我最初的陈述非常接近（虽然不太易读且速度较慢）！

（这个函数被称为“subgrups”，因为问题最初要求查找“所有子群”）

- rlms

Answer 3

考虑使用more_itertools.set_partitions。

已知条件：

import more_itertools as mit


lst = [1, 2, 3]

代码

展开一组 k 个集合划分：

[part for k in range(1, len(lst) + 1) for part in mit.set_partitions(lst, k)]

输出

 [((1, 2, 3),),
  ((1,), (2, 3)),
  ((2,), (1, 3)),
  ((3,), (1, 2)),
  ((1,), (2,), (3,))]

more_itertools 是一个第三方软件包。通过 > pip install more_itertools 命令进行安装。

- pylang

Answer 4

如果有人想要用JS实现此代码，那么这确实需要花费一些时间来实现。我曾经在JS中与“值和引用”进行了搏斗。

算法与@alexis上面解释的相同。

函数deepCopy是克隆一个数组，而不是将其复制到一个数组中。

function deepCopy(val){
    return JSON.parse(JSON.stringify(val));
}

function partitions(arr) {
    var results = [];

    if (arr.length == 0) {
        results.push([[]]);
        return results;
    }

    if (arr.length == 1) {
        results.push(new Array(arr));
        return results;//[[[1]]]
    }

    var last = arr[arr.length - 1];
    var sub = partitions(arr.slice(0, arr.length - 1));//remove the last item

    //partitions(2) => [ [ [ 's1', 's2' ] ], [ [ 's1' ], [ 's2' ] ] ]
    //val => [ [ 's1', 's2' ] ] or [ [ 's1' ], [ 's2' ] ]
    //set => [ 's1', 's2' ] or [ 's1' ], [ 's2' ]
    sub.map((partition) => {
        //val => each partition
        //1) insert the "last" into each set, together with the rest of sets in the same partition makes a new partition
        partition.map((set) => {
            //set=>each set of one particular partition
            set.push(last);
            results.push(deepCopy(partition));
            set.pop();
        });
        //2), insert the "last" as a singlton set into the partition, make it a new partition
        partition.push([last]);
        results.push(deepCopy(partition));
        partition.pop();
    });

    return results;
}

var arr = ["s1", "s2", "s3"];
const results = partitions(arr);
console.log(results);

输出：

[
  [ [ 's1', 's2', 's3' ] ],
  [ [ 's1', 's2' ], [ 's3' ] ],
  [ [ 's1', 's3' ], [ 's2' ] ],
  [ [ 's1' ], [ 's2', 's3' ] ],
  [ [ 's1' ], [ 's2' ], [ 's3' ] ]
]

- user1310312

Answer 5

我将alexis的答案改为使用循环而不是递归。代码不太容易理解，但现在也应该可以处理非常大的数据集：

def partition(collection):
    collection_except_last = reversed(collection[:-1])
    only_last = list(collection[-1:])

    # start with the partition for a 1-element collection and then add elements
    partitions = [[only_last]]
    for element in collection_except_last:
        refined_partitions = []
        for partition_ in partitions:
            # insert `element` in each of the subpartition's subsets
            for n, subset in enumerate(partition_):
                refined = partition_[:n] + [[element] + subset] + partition_[n + 1 :]
                refined_partitions.append(refined)
            # put `element` in its own subset
            refined_partitions.append([[element]] + partition_)
        partitions = refined_partitions
    return partitions

- user16912097

---

集合：Sequence[T] ? - jokoon

我移除了那些序列和列表，但速度仍然很慢。 - jokoon