ここでは配列を2つのサブセットに分けることができるかどうかを調べる方法を説明します。サブセットが利用可能な場合は、両方のサブセットの要素の合計が同じである必要があります。真を返します。同じsum-pythonを持つサブセット
For array = [8, 6, 3, 5], the output should be sub(array) = true
8の和を有する2つのサブセットにこの配列を分割することが可能である[8]、[3,5]。
`
はここでブルートフォースソリューションです。ドキュメント内のItertools Recipesのpowersetレシピを使用して、すべてのサブセットを生成します。 itertools.groupbyを使用して合計でソートし、グループ化します。最後に、同じ合計を持つすべてのサブセットのペアをチェックして、交差していないペアを見つけます。
from itertools import chain, combinations, groupby
def equal_sum_partitions(seq):
subsets = chain.from_iterable(combinations(seq, r) for r in range(len(seq)+1))
for k, g in groupby(sorted(subsets, key=sum), key=sum):
group = [set(u) for u in g]
if len(group) > 1:
for u, v in combinations(group, 2):
if not u & v:
print(k, (u, v))
# test
equal_sum_partitions([2, 4, 8, 6, 3, 5])
出力
5 ({5}, {2, 3})
6 ({6}, {2, 4})
7 ({2, 5}, {3, 4})
8 ({8}, {2, 6})
8 ({8}, {3, 5})
8 ({2, 6}, {3, 5})
9 ({4, 5}, {3, 6})
10 ({8, 2}, {4, 6})
10 ({4, 6}, {2, 3, 5})
11 ({8, 3}, {5, 6})
11 ({8, 3}, {2, 4, 5})
13 ({8, 5}, {3, 4, 6})
14 ({8, 6}, {2, 3, 4, 5})
14 ({8, 2, 4}, {3, 5, 6})
入力配列に重複要素がある場合はどうなりますか？例えば'[8、8、2、1、3]'合計11の2つのサブセットがありますが、このメソッドはそれらを捕捉しません。 – asongtoruin
@asongtoruin真実ですが、重複していない真のセットを扱っていると仮定することにしました。 ;）元のセットに2つの '8 'が含まれている場合、'（{8}、{8}） 'は有効なパーティションとしてカウントされますか？ –
itertoolsの優れた使用方法。しかし、複雑なので、サブセットを作成した後、それらを繰り返し処理し、 'sum（sub）== sum（seq）/ 2'をチェックすることができます。 – JanHak
は、私は解決策を見つけたが、それは大きな入力に対してメモリエラーが発生します:(
def subs(l):
if l == []:
return [[]]
x = subs(l[1:])
return x + [[l[0]] + y for y in x]
def sub(arr):
ls=[]
ls=subs(arr)
for i in ls:
if(sum(list(set(arr)-set(i)))==sum(i)):
return True
return False
をあなたはhttpsを見てきました：// EN。 wikipedia.org/wiki/Subset_sum_problemあなたの質問は、いくつかの派手な動的プログラミングを必要とするより高度な問題です、私はあなたのためにそれを行うことができますPythonライブラリがあるとは思わない:( – jcr
Okayありがとう...... – yzcop
http://stackoverflow.com/questions/6012963/subset-sum-problem; http://stackoverflow.com/questions/23087820/python-subset-sum –