2

因此，如果我有数字 [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] 等。

4

4 回答 4

1

在Code Review中查看 Python 中的答案。

于 2013-03-10T00:50:37.737 回答
0

user3569 在Code Review上的解决方案为下面的测试用例生成了五个 2 元组，而不是专门的 3 元组。但是，删除对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 的解决方案，由 Adeel Zafar Soomro 在同一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 个。我还没有仔细检查输出以确定哪个输出是正确的。

于 2013-03-10T01:59:32.340 回答
0

这是 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]]]
于 2013-03-10T06:06:24.367 回答
0

Python解决方案：

pip install PartitionSets

然后：

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

PartitionSets 的实现似乎非常快，但是很遗憾您不能将分区数量作为参数传递，因此您需要从所有子分区中过滤出您的 k 集分区。

您可能还想查看： researchgate 上的类似主题。

于 2014-10-17T16:21:52.030 回答