找到對應列出資金

鑑於兩個數字表和彙總的列表（沒有在任何特定的順序）的對集：找到對應列出資金

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

我如何才能找到對d的所有集合，其中d[k] = (a[i], b[j])這樣c[k] = a[i] + b[j]哪裏對使用a和b而沒有替換？（所有的列表可以有重複）

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

對於c = [7,7,7]：

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

（1個答案，因爲所有的排列基本上等同）

我想和長度的列表來做到這一點〜 500，所以一個天真的匹配/回溯搜索是不可能的。

來源

2013-02-28 georgeyiu

你想要一組序列序列，其中序列中的每個序列的總數都與序列c相匹配？而且，在第一個例子中，[（1,5），（1,6），（2,6）]等等 - 還有更多這樣的 - 也包括在內嗎？ – 2013-02-28 09:44:10

沒有替換。我試圖解決的問題是，每個列表都包含幾十名學生。我可以訪問每個列表和兩者的總和，但想知道總分數，可能的子分數。如果問題更容易解決（或增加解決方案的可能性），我可以訪問這些列表中的N個，並可以向數據庫查詢任何子集的總計列表。 – georgeyiu 2013-02-28 09:48:58

在維基百科中將此問題描述爲[數字三維匹配]（http://en.wikipedia.org/wiki/Numerical_3-dimensional_matching）。這是NP完整的。 – 2013-02-28 11:25:12

這是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; 
}

來源

2013-03-06 04:11:02 brooksbp

好的，有修剪的蠻力方法。這需要O（N^3）

爲了便於演示，我將通過擁有的一個和b

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

而且我總和的N×N的平方想建立c = {6,7,8}
我在S找到'6'。我將其刪除，並標記它的行和列不可用

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

Solution = { (1,5) }

然後我試圖找到一個 '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) }

第1循環（'6'的循環）將繼續並找到另一個匹配：（2,4）。這將形成第二個解決方案{（2,4）（1,6）（3,5）}

現在，一種改進方法是使用一些動態編程：找出所有可能的組合預先結果。

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），其中S_li表示S_I的長度。

This may在平均情況下運行速度更快。它也會正確處理c = {7,7,7}的情況。

這幾乎是我得到的。

來源

2013-06-28 06:02:34 aec

找到對應列出資金

回答

相關問題