我有一個數字列表，如何生成所有獨特的K分區？

Question

所以如果我有數字[1,2,2,3]，我想要k = 2分區，我會[1] [2,2,3]，[1,2] [2,3]， [2,2] [1,3]，[2] [1,2,3]，[3] [1,2,2]等

Answer 1

在Code Review參見在Python一個答案。

Answer 2

user3569的在Code Review溶液產生的，而不是排他地3元組5個2元組爲下面的試驗情況下，。但是，除去返回元組的frozenset()調用將導致代碼僅返回3元組。修改後的代碼如下：

from itertools import chain, combinations 

def subsets(arr): 
    """ Note this only returns non empty subsets of arr""" 
    return chain(*[combinations(arr,i + 1) for i,a in enumerate(arr)]) 

def k_subset(arr, k): 
    s_arr = sorted(arr) 
    return set([i for i in combinations(subsets(arr),k) 
       if sorted(chain(*i)) == s_arr]) 

s = k_subset([2,2,2,2,3,3,5],3) 

for ss in sorted(s): 
    print(len(ss)," - ",ss) 

正如user3569所說：「它運行速度很慢，但相當簡潔」。

（編輯：見下文Knuth的溶液）

的輸出是：

3 - ((2,), (2,), (2, 2, 3, 3, 5)) 
3 - ((2,), (2, 2), (2, 3, 3, 5)) 
3 - ((2,), (2, 2, 2), (3, 3, 5)) 
3 - ((2,), (2, 2, 3), (2, 3, 5)) 
3 - ((2,), (2, 2, 5), (2, 3, 3)) 
3 - ((2,), (2, 3), (2, 2, 3, 5)) 
3 - ((2,), (2, 3, 3), (2, 2, 5)) 
3 - ((2,), (2, 3, 5), (2, 2, 3)) 
3 - ((2,), (2, 5), (2, 2, 3, 3)) 
3 - ((2,), (3,), (2, 2, 2, 3, 5)) 
3 - ((2,), (3, 3), (2, 2, 2, 5)) 
3 - ((2,), (3, 5), (2, 2, 2, 3)) 
3 - ((2,), (5,), (2, 2, 2, 3, 3)) 
3 - ((2, 2), (2, 2), (3, 3, 5)) 
3 - ((2, 2), (2, 3), (2, 3, 5)) 
3 - ((2, 2), (2, 5), (2, 3, 3)) 
3 - ((2, 2), (3, 3), (2, 2, 5)) 
3 - ((2, 2), (3, 5), (2, 2, 3)) 
3 - ((2, 3), (2, 2), (2, 3, 5)) 
3 - ((2, 3), (2, 3), (2, 2, 5)) 
3 - ((2, 3), (2, 5), (2, 2, 3)) 
3 - ((2, 3), (3, 5), (2, 2, 2)) 
3 - ((2, 5), (2, 2), (2, 3, 3)) 
3 - ((2, 5), (2, 3), (2, 2, 3)) 
3 - ((2, 5), (3, 3), (2, 2, 2)) 
3 - ((3,), (2, 2), (2, 2, 3, 5)) 
3 - ((3,), (2, 2, 2), (2, 3, 5)) 
3 - ((3,), (2, 2, 3), (2, 2, 5)) 
3 - ((3,), (2, 2, 5), (2, 2, 3)) 
3 - ((3,), (2, 3), (2, 2, 2, 5)) 
3 - ((3,), (2, 3, 5), (2, 2, 2)) 
3 - ((3,), (2, 5), (2, 2, 2, 3)) 
3 - ((3,), (3,), (2, 2, 2, 2, 5)) 
3 - ((3,), (3, 5), (2, 2, 2, 2)) 
3 - ((3,), (5,), (2, 2, 2, 2, 3)) 
3 - ((5,), (2, 2), (2, 2, 3, 3)) 
3 - ((5,), (2, 2, 2), (2, 3, 3)) 
3 - ((5,), (2, 2, 3), (2, 2, 3)) 
3 - ((5,), (2, 3), (2, 2, 2, 3)) 
3 - ((5,), (2, 3, 3), (2, 2, 2)) 
3 - ((5,), (3, 3), (2, 2, 2, 2)) 

Knuth的溶液，如通過阿迪爾扎法爾蘇姆羅同一Code Review頁上實現可稱爲如果沒有重複如下期望：

s = algorithm_u([2,2,2,2,3,3,5],3) 
ss = set(tuple(sorted(tuple(tuple(y) for y in x) for x in s))) 

我沒有超時，但Knuth的解決方案是明顯更快，即使是在這個測試案例。

但是，它返回63個元組，而不是由user3569的解決方案返回的41個元組。我還沒有經過足夠的輸出來確定哪個輸出是正確的。

Answer 3

下面是Haskell的一個版本：

import Data.List (nub, sort, permutations) 

parts 0 = [] 
parts n = nub $ map sort $ [n] : [x:xs | x <- [1..n`div`2], xs <- parts(n - x)] 

partition [] ys result = sort $ map sort result 
partition (x:xs) ys result = 
    partition xs (drop x ys) (result ++ [take x ys]) 

partitions xs k = 
    let variations = filter (\x -> length x == k) $ parts (length xs) 
    in nub $ concat $ map (\x -> mapVariation x (nub $ permutations xs)) variations 
    where mapVariation variation = map (\x -> partition variation x []) 


OUTPUT: 
*Main> partitions [1,2,2,3] 2 
[[[1],[2,2,3]],[[1,2,3],[2]],[[1,2,2],[3]],[[1,2],[2,3]],[[1,3],[2,2]]] 

Answer 4

Python的解決方案：

pip install PartitionSets 

然後：

import partitionsets.partition 
filter(lambda x: len(x) == k, partitionsets.partition.Partition(arr)) 

的PartitionSets實施似乎是相當快速但它是一個遺憾，你可以不會將分區數量作爲參數傳遞，因此您需要從所有子集p中篩選您的k-集分區artitions。

您可能還需要查看： similar topic on researchgate。