所以如果我有数字[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个回答
1
在Python代码审查中查看答案，请访问Code Review。
- o17t H1H' S'k
7
这段代码生成重复项，仅采用连续子集。 - KaliMa
为了避免重复，你可以这样做：set(results) - o17t H1H' S'k
你看过 Adeel Zafar Soomro 的第一个答案中的代码了吗？ - o17t H1H' S'k
在寻找创意的过程中，发现了一个已有的解决方案真是太棒了！另外，用户3569提供的解决方案可能会比较慢，但我已经运行过它，并且确实生成了非连续的子集，且没有重复。 - Simon
@Simon 那段代码并不能正常工作，因为有时它不会返回 k 元组而是一个 k-1 元组。编辑：它还受到内存的严重限制。 - KaliMa
显示剩余2条评论
0
Python解决方案：
pip install PartitionSets
然后：
import partitionsets.partition
filter(lambda x: len(x) == k, partitionsets.partition.Partition(arr))
PartitionSets 的实现似乎非常快，但是很遗憾你不能将分区数作为参数传递，因此你需要从所有子集分区中筛选出你的 k 集分区。
你可能还想看一下： 研究门户上类似的话题。
- fakej Gazeta.pl
0
用户3569在代码审查中提供的解决方案对于下面的测试用例产生了五个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)
正如用户3569所说，“它运行得相当慢，但相当简洁”。
（编辑：请参见下面的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))
如果不需要重复项，则可以按照 Adeel Zafar Soomro 在同一Code Review页面上实现的方式来调用 Knuth 的解决方案：
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个。我还没有仔细检查输出以确定哪个输出是正确的。
- Simon
6
这仍然存在严重的内存和速度限制。 - KaliMa
鉴于我们在寻找解决方案时遇到的困难，尽管存在内存和速度限制，但这个解决方案至少可以成为自动化测试的基础，以测试更快、使用更少内存的解决方案。我非常支持先让代码正确运行，然后再考虑速度。我认为下一步可能是根据此问题的规格调整 Knuth 的解决方案，因为如果我们能让它适用于这个问题，Knuth 的解决方案将会更快。 - Simon
有没有一种方法可以修改Knuth算法，以避免创建太多的重复项？ - KaliMa
我已经编辑了我的答案，包括调用Knuth算法的代码，如在Code Review页面上所述，同时删除重复项。 - Simon
我认为这仍会生成重复项（事后删除它们并不太难），我的意思是是否有一种直接生成唯一解决方案的方法？ - KaliMa
Soomro 实现的 Knuth 算法会生成重复项，但是（如果输出正确，我们还需要验证），它可以非常快速地生成并且事后删除它们也不费时，因此它是我们之前考虑的算法的改进。 - Simon
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]]]
- גלעד ברקן
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接