複数のサブセット合計の計算

Question

私は2つのセットを持っています。セットAには乱数セットが含まれ、セットBのエレメントはセットAのサブセットの合計です。例えば

、

A = [8, 9, 15, 15, 33, 36, 39, 45, 46, 60, 68, 73, 80, 92, 96] 

B = [183, 36, 231, 128, 137] 

私はこのようなデータをどのサブセットの合計である数見つけたいです。

S = [[45, 46, 92], [36], [8, 15, 39, 73, 96], [60, 68], [9, 15, 33, 80]] 

私はPythonで本当にダムブルートフォースコードを書くことができました。

このコードは小規模なデータではうまく機能しますが、データの計算には10億年かかる（数字は71個、合計は10個）。

より良いアルゴリズムや最適化を使用することができます。

私の悪い英語と恐ろしい不十分なコードのため申し訳ありません。

---

編集：申し訳ありませんが、私は問題を正確に記述していないことに気付きました。

A内のすべての単一の要素がBのelemensを製造するために使用されているように、sum(A) == sum(B)

はまた、セットAのパーティションでなければならないSを設定します。

Answer 1

これはサブセットサム問題として知られており、よく知られているNP完全問題です。基本的に効率的なソリューションはありません。あなたの数Nは、動的プログラミングを使用して、擬似的多項式アルゴリズムがあり、あまり大きくない場合しかし、たとえばhttps://en.wikipedia.org/wiki/Subset_sum_problem

を参照してください： あなたが左から右にリストAを読んで、なんとかしている和のリストを保持し、与えられたAに対して実行可能な数を知っていれば、A + [a]に対して実行可能な数を簡単に得ることができます。したがって、動的プログラミング。それはあなたがそこに与えたサイズの問題のために十分速いのが普通です。 OP編集後

def subsetsum(A, N): 
    res = {0 : []} 
    for i in A: 
     newres = dict(res) 
     for v, l in res.items(): 
      if v+i < N: 
       newres[v+i] = l+[i] 
      elif v+i == N: 
       return l+[i] 
     res = newres 
    return None 

その後

>>> A = [8, 9, 15, 15, 33, 36, 39, 45, 46, 60, 68, 73, 80, 92, 96] 
>>> subsetsum(A, 183) 
[15, 15, 33, 36, 39, 45] 

---

：ここ

はPythonの迅速なソリューションです

は今、私が正しくあなたの問題を理解し、私はまだだと思いますあなたの問題は効率的なサブセット和ソルバーを持っていれば、効率的に解くことができます：私は分裂と征服を使うB上のn：

• カットB、ほぼ等しい2つの片にB1とB2
• は、Sは、その和（B1）の和に等しいすべてのサブセットについてのうち、検索にサブセット和ソルバーを使用。それぞれのそのようなSについて
• ：
  • 呼び出しを再帰的に（S、B1）を解決し、解決 - の両方を使用すると、

しかし解決策を持って成功した場合

を（A S、B2）あなたの（71,10）問題は、私が提案したダイナミックプログラミングソリューションの範囲外です。ところで

---

は、ここでは分割統治を使用して迅速な問題の解決ないですが、これはすべてのソリューションを取得するために私の動的なソルバーの正しい適応が含まれています。そして、

class NotFound(BaseException): 
    pass 

from collections import defaultdict 
def subset_all_sums(A, N): 
    res = defaultdict(set, {0 : {()}}) 
    for nn, i in enumerate(A): 
     # perform a deep copy of res 
     newres = defaultdict(set) 
     for v, l in res.items(): 
      newres[v] |= set(l) 
      for v, l in res.items(): 
       if v+i <= N: 
        for s in l: 
         newres[v+i].add(s+(i,)) 
         res = newres 
         return res[N] 

def list_difference(l1, l2): 
    ## Similar to merge. 
    res = [] 
    i1 = 0; i2 = 0 
    while i1 < len(l1) and i2 < len(l2): 
     if l1[i1] == l2[i2]: 
      i1 += 1 
      i2 += 1 
     elif l1[i1] < l2[i2]: 
      res.append(l1[i1]) 
      i1 += 1 
     else: 
      raise NotFound 
      while i1 < len(l1): 
       res.append(l1[i1]) 
       i1 += 1 
       return res 

def solve(A, B): 
    assert sum(A) == sum(B) 
    if not B: 
     return [[]] 
     res = [] 
     ss = subset_all_sums(A, B[0]) 
     for s in ss: 
      rem = list_difference(A, s) 
      for sol in solve(rem, B[1:]): 
       res.append([s]+sol) 
       return res 

を：

>>> solve(A, B) 
[[(15, 33, 39, 96), (36,), (8, 15, 60, 68, 80), (9, 46, 73), (45, 92)], 
[(15, 33, 39, 96), (36,), (8, 9, 15, 46, 73, 80), (60, 68), (45, 92)], 
[(8, 15, 15, 33, 39, 73), (36,), (9, 46, 80, 96), (60, 68), (45, 92)], 
[(15, 15, 73, 80), (36,), (8, 9, 33, 39, 46, 96), (60, 68), (45, 92)], 
[(15, 15, 73, 80), (36,), (9, 39, 45, 46, 92), (60, 68), (8, 33, 96)], 
[(8, 33, 46, 96), (36,), (9, 15, 15, 39, 73, 80), (60, 68), (45, 92)], 
[(8, 33, 46, 96), (36,), (15, 15, 60, 68, 73), (9, 39, 80), (45, 92)], 
[(9, 15, 33, 46, 80), (36,), (8, 15, 39, 73, 96), (60, 68), (45, 92)], 
[(45, 46, 92), (36,), (8, 15, 39, 73, 96), (60, 68), (9, 15, 33, 80)], 
[(45, 46, 92), (36,), (8, 15, 39, 73, 96), (15, 33, 80), (9, 60, 68)], 
[(45, 46, 92), (36,), (15, 15, 60, 68, 73), (9, 39, 80), (8, 33, 96)], 
[(45, 46, 92), (36,), (9, 15, 15, 39, 73, 80), (60, 68), (8, 33, 96)], 
[(9, 46, 60, 68), (36,), (8, 15, 39, 73, 96), (15, 33, 80), (45, 92)]] 

>>> %timeit solve(A, B) 
100 loops, best of 3: 10.5 ms per loop 

ここでは最適化されていますが、問題のこのサイズではかなり高速です。

Answer 2

完全な解決方法は、すべての方法を計算して合計します。 速度とメモリの使用のための特性セットとしてintsを使用します：19='0b10011'は[A[0],A[1],A[4]]=[8,9,33]をここに表します。

A = [8, 9, 15, 15, 33, 36, 39, 45, 46, 60, 68, 73, 80, 92, 96] 
B =[183, 36, 231, 128, 137] 

def subsetsum(A,N): 
    res=[[0]]+[[] for i in range(N)] 
    for i,a in enumerate(A): 
     k=1<<i   
     stop=[len(l) for l in res] 
     for shift,l in enumerate(res[:N+1-a]): 
      n=a+shift 
      ln=res[n] 
      for s in l[:stop[shift]]: ln.append(s+k) 
    return res 

res = subsetsum(A,max(B)) 
solB = [res[b] for b in B] 
exactsol = ~-(1<<len(A)) 

def decode(answer): 
    return [[A[i] for i,b in enumerate(bin(sol)[::-1]) if b=='1'] for sol in answer] 

def solve(i,currentsol,answer): 
     if currentsol==exactsol : print(decode(answer)) 
     if i==len(B): return 
     for sol in solB[i]: 
       if not currentsol&sol: 
        answer.append(sol) 
        solve(i+1,currentsol+sol,answer) 
        answer.pop() 

2つ15は同じサブセットにないときよりも

solve(0,0,[]) 

[[9, 46, 60, 68], [36], [8, 15, 39, 73, 96], [15, 33, 80], [45, 92]] 
[[9, 46, 60, 68], [36], [8, 15, 39, 73, 96], [15, 33, 80], [45, 92]] 
[[8, 15, 15, 33, 39, 73], [36], [9, 46, 80, 96], [60, 68], [45, 92]] 
[[9, 15, 33, 46, 80], [36], [8, 15, 39, 73, 96], [60, 68], [45, 92]] 
[[9, 15, 33, 46, 80], [36], [8, 15, 39, 73, 96], [60, 68], [45, 92]] 
[[15, 15, 73, 80], [36], [9, 39, 45, 46, 92], [60, 68], [8, 33, 96]] 
[[15, 15, 73, 80], [36], [8, 9, 33, 39, 46, 96], [60, 68], [45, 92]] 
[[45, 46, 92], [36], [15, 15, 60, 68, 73], [9, 39, 80], [8, 33, 96]] 
[[45, 46, 92], [36], [9, 15, 15, 39, 73, 80], [60, 68], [8, 33, 96]] 
[[45, 46, 92], [36], [8, 15, 39, 73, 96], [60, 68], [9, 15, 33, 80]] 
[[45, 46, 92], [36], [8, 15, 39, 73, 96], [15, 33, 80], [9, 60, 68]] 
[[45, 46, 92], [36], [8, 15, 39, 73, 96], [60, 68], [9, 15, 33, 80]] 
[[45, 46, 92], [36], [8, 15, 39, 73, 96], [15, 33, 80], [9, 60, 68]] 
[[15, 33, 39, 96], [36], [8, 15, 60, 68, 80], [9, 46, 73], [45, 92]] 
[[15, 33, 39, 96], [36], [8, 9, 15, 46, 73, 80], [60, 68], [45, 92]] 
[[15, 33, 39, 96], [36], [8, 15, 60, 68, 80], [9, 46, 73], [45, 92]] 
[[15, 33, 39, 96], [36], [8, 9, 15, 46, 73, 80], [60, 68], [45, 92]] 
[[8, 33, 46, 96], [36], [15, 15, 60, 68, 73], [9, 39, 80], [45, 92]] 
[[8, 33, 46, 96], [36], [9, 15, 15, 39, 73, 80], [60, 68], [45, 92]] 

通知は、溶液が2倍になります。 1秒間に

A=[1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009, 1010, 1011, 
    1012, 1013, 1014, 1015, 1016, 1017, 1018, 1019, 1020, 1021, 1022, 1023, 
    1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 1032, 1033, 1034, 1035, 
    1036, 1037, 1038, 1039, 1040, 1041, 1042, 1043, 1044, 1045, 1046, 1047, 
    1048, 1049] 

B=[5010, 5035, 5060, 5085, 5110, 5135, 5160, 5185, 5210, 5235] 

：

それはユニークなソリューションの問題を解決します。残念ながら、（71,10）問題にはまだ十分に最適化されていません。

しかし、純粋な動的計画法の精神でもう一つ、：：

@functools.lru_cache(max(B)) 
def solutions(n): 
    if n==0 : return set({frozenset()}) #{{}} 
    if n<0 : return set() 
    sols=set() 
    for i,a in enumerate(A): 
      for s in solutions(n-a): 
       if i not in s : sols.add(s|{i}) 
    return sols 

def decode(answer): return([[A[i] for i in sol] for sol in answer]) 

def solve(B=B,currentsol=set(),answer=[]): 
    if len(currentsol)==len(A) : sols.append(decode(answer)) 
    if B: 
     for sol in solutions(B[0]): 
      if set.isdisjoint(currentsol,sol): 
       solve(B[1:],currentsol|sol,answer+[sol]) 

sols=[];solve()