考えると合計

Question

2つの数のリストと合計のリスト（特定の順序でなし）のリストに対応ペアのセット検索：

a = [1,2,3] 
b = [4,5,6] 
c = [6,7,8] 

がどのように私はd[k] = (a[i], b[j])、このようなペアdのすべてのセットを見つけることができますがそのc[k] = a[i] + b[j]ペアは置換なしでaとbから使用されますか？ c = [7,7,7]については

d = [(1,5), (3,4), (2,6)] 
d = [(2,4), (1,6), (3,5)] 

（すべてのリストは、重複を持つことができます）：

d = [(1,6), (2,5), (3,4)] 

（1答すべての順列は、本質的に等価であるため）

が、私は長さのリストでこれを行うにはしたいと思います〜 500となっていますので、素朴なマッチング/バックトラック検索が問題になりません。ここで

Answer 1

は、C++でのブルートフォースアプローチです。それは、等価置換を除去しない。 c = [7,7,7]である。

#include <vector> 
#include <iostream> 
#include <algorithm> 
#include <utility> 

using namespace std; 

// numerical 3d match: x + y + z = b where                       
// x = a, y = b, z = -c, b = 0                          
template <typename T> 
vector<pair<vector<T>, vector<T> > > n3dmatch(vector<T> a, vector<T> b, vector<T> c) { 
    vector<pair<vector<T>, vector<T> > > result; 
    if (a.size() != b.size() || b.size() != c.size()) return result; 

    vector<vector<T> > ap, bp; 
    sort(a.begin(), a.end()); 
    sort(b.begin(), b.end()); 
    do { ap.push_back(a); } while (next_permutation(a.begin(), a.end())); 
    do { bp.push_back(b); } while (next_permutation(b.begin(), b.end())); 

    for (int i = 0; i < ap.size(); i++) { 
    for (int j = 0; j < ap.size(); j++) { 
     bool match = true; 
     for (int k = 0; k < a.size(); k++) { 
     if ((ap[i][k] + bp[j][k]) != c[k]) { 
      match = false; break; 
     } 
     } 
     if (match) result.push_back({ ap[i], bp[j] }); 
    } 
    } 
    return result; 
} 

int main(int argc, char *argv[]) { 
    vector<int> a = { 1, 2, 3 }; 
    vector<int> b = { 4, 5, 6 }; 
    vector<int> c = { 6, 7, 8 }; 
    //vector<int> c = { 7, 7, 7 };                         
    auto result = n3dmatch(a, b, c); 
    for (int i = 0; i < result.size(); i++) { 
    vector<int> &a = result[i].first; 
    vector<int> &b = result[i].second; 
    for (int j = 0; j < a.size(); j++) cout << a[j] << " "; cout << endl; 
    for (int j = 0; j < b.size(); j++) cout << b[j] << " "; cout << endl; 
    cout << "-" << endl; 
    } 
    return 0; 
} 

Answer 2

わかりやすく、枝刈りを使用しています。これはO（N^3）のデモを容易にするため

を取り、私はとB

S: 
+ | 4 5 6 
--|------- 
1 | 5 6 7 
2 | 6 7 8 
3 | 7 8 9 

そして私はの合計を持っているNバイN乗を通過します= {6,7,8}
Cを構築するために見ている私はSに '6' を見つけます。 Iその後、私は '7'

S: 
+ | 4 5 6 
--|------- 
1 |/X/
2 |// 8 
3 | X// 

Solution = { (1,5) (3,4) } 

そして最後に '6'

S: 
+ | 4 5 6 
--|------- 
1 |/X/
2 |// X 
3 | X// 

Solution = { (1,5) (3,4) (2,6) } 

第一を探してみてください、それを削除し、使用できなく

S: 
+ | 4 5 6 
--|------- 
1 |/X/
2 | 6/8 
3 | 7/9 

Solution = { (1,5) } 

としてその行と列をマークループ（ '6'のためのもの）は続行し、別の一致を見つける：（2,4）。与えるすべての可能な組み合わせを見つける：これは、第2の溶液{（2,4）、（1,6）、（3,5）}

さて、これを改善する1つの方法は、いくつかの動的プログラミングを使用しているを形成しますあらかじめ結果S_liがS_Iの長さを示し

Given c={ 6 7 8}, create sets S_x where x is {6,7,8} and 
    S_x = { (i,j) } such that S[i][j]=x 
So: 
    S_6 = { (1,2) (2,1) } 
    S_7 = { (1,3) (2,2) (3,1) } 
    S_8 = { (2,3) (3,2) } 

そして今、与えられたヒューリスティックと同じアルゴリズムはO（S_l1 * S_l2 * ... S_lN）で実行されます。

このは速い平均場合の要因を実行することができます。 また、c = {7,7,7}の場合も正しく処理されます。ほとんどすべて私が得たのです

。