我有一个数字列表，如何生成所有独特的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。