使用 Python 设置分区-IT科技

摘要：问题描述：我有一系列[1,2,3]我想使用数组的所有元素做出所有可能的组合：结果：[[1], [2], [3]] [[1,2], [3]] [[1], [2,3]] [[1,3], [2]] [[1,2,3]] 解决方案 1：由于这个好问题又被重新提出，这里有一个新的答案。这个问题是递归解决的：如果你已经有了...

问题描述：

我有一系列[1,2,3]

我想使用数组的所有元素做出所有可能的组合：

结果：

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

解决方案 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]]

解决方案 2：

考虑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。

解决方案 3：

与我的评论不同，我无法快速找到基于 itertools 的相对快速的解决方案！编辑：这不再完全正确，我有一个相当短（但缓慢且难以阅读）的解决方案，主要使用 itertools，请参阅答案的结尾。这是我得到的：

我们的想法是，找到所有加起来等于列表长度的整数组合，然后获取具有该长度切片的列表。

例如，对于长度为 3 的列表，组合或分区为 (3)、(2, 1)、(1, 2) 和 (1, 1, 1)。因此，我们返回列表的前 3 个项目；前 2 个，然后是下一个 1；第一个 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]]

然后，您只需subgrups对原始列表的每个 3 长度排列进行调用，例如对中的每个排列进行调用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因为问题最初要求找到“所有子群”，所以调用这些函数）

解决方案 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' ] ]
]

解决方案 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

解决方案 6：

通过稍微不同的解决问题来回答：使用 [1,2,3] 的数学分割

就我而言，我觉得我们需要一个可以生成 [1,2,3] 数学分区的工具。此分区包含所有分组 1、2 和 3 的方式，包括 []。itertools 和 more-itertools 似乎缺少这种功能。

这里有一个工作代码：

def convert_config_into_set(collection, config):
    """
    a 'config' is a one-hot encoding of one set of
    the mathematical partition of collection
    e.g.
    collection = {1, 2, 3}
    config = (0, 1, 1)
    output = {2, 3}
    """
    return {p for p, k in zip(collection, range(len(config))) if config[k] == 1}


def get_set_config_partition(collection):
    """
    list of all one-hot encoding of the sets of
    the mathematical partition of collection
    e.g.
    collection = {1, 2}
    output = [(0, 0), (0, 1), (1, 0), (1, 1)]
    """
    return [p for p in itertools.product(*[[0, 1]]*len(collection))]


def generate_set_partition(collection):
    """
    return the mathematical partition of `collection`
    e.g.
    collection = {1, 2}
    output = [set(), {1}, {2}, {1, 2},]
    """
    return [
        convert_config_into_set(
            collection=collection,
            config=config,
        )
        for config in get_set_config_partition(collection)
    ]

if __name__ == '__main__':
    generate_set_partition(collection={1, 2, 3})

输出

[set(), {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}]

有了此代码，问题的答案就如下：生成数学分区并省略空集。