在Python中设置分区

Question

在Python中设置分区我有一个数组 [1,2,3]我想使用数组的所有元素进行所有可能的组合：结果：[[1], [2], [3]][[1,2], [3]][[1], [2,3]][[1,3], [2]][[1,2,3]]

Answer 1

与我建议的评论不同，我无法快速找到基于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])IS [[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是因为最初要求查找“所有子项目”的问题）

Answer 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。