组分区在Python

Question

我有[1,2,3]

我想一个数组进行使用阵列中的所有元素所有可能的组合：

结果：

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

Answer 1

不像我的意见建议，我无法快速找到基于itertools的相对较快的解决方案！编辑：这不再是非常真实的，我有一个相当短的（但缓慢和不可读）解决方案大部分使用itertools，看到答案的结尾。这是我得到的代替：

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

E.g.对于长度为3的列表，组合或分区是（3），（2,1），（1,2）和（1,1,1）。所以我们返回列表的前三项;第一个2，然后是第二个1;第一个1然后是下一个2和第一个1，然后是下一个1，然后是下一个1.

我从here得到整数分区的代码。但是，分区函数并不返回分区的所有排列（即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] 

然后从this答案，我们让我们的整数分区功能：

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因为这个问题原本寻问“所有subgrups”）

Answer 2

由于这个有趣的问题已经被带回生活，这里是一个新的答案。

的问题是递归解决：如果你已经拥有的N-1元素的分区，你怎么用它来划分ň元素？将n'th元素放置在其中一个现有子集中，或将其添加为新的单例子集。这一切都需要;没有itertools，无需套，无重复输出，总共才ň调用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]]