組分區在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]]