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

Code Reviewでの user3569 のソリューションは、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 が言うように、「実行速度はかなり遅いですが、かなり簡潔です」。

（編集：クヌースの解決策については以下を参照）

出力は次のとおりです。

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 によって実装されている 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 のソリューションの方が目に見えて高速です。

ただし、user3569 のソリューションによって返される 41 ではなく、63 のタプルが返されます。どの出力が正しいかを確立するのに十分なほど出力を詳しく調べていません。

于 2013-03-10T01:59:32.340 に答える
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 に答える
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 に答える