Tìm tập hợp các cặp tương ứng với danh sách các khoản tiền

Question

Với hai danh sách các số và danh sách tổng số (không có trong bất kỳ thứ tự cụ thể):

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

Làm thế nào tôi có thể tìm thấy tất cả các bộ cặp d nơi d[k] = (a[i], b[j]) như vậy rằng c[k] = a[i] + b[j] nơi các cặp được sử dụng từ a và b mà không cần thay thế? (Tất cả các danh sách có thể có bản sao)

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

Đối c = [7,7,7]:

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

(1 trả lời bởi vì tất cả các hoán vị cơ bản là tương đương)

Tôi muốn làm điều này với danh sách dài ~ 500, do đó, một kết hợp ngây thơ/tìm kiếm backtracking là ra câu hỏi.

Answer 1

Đây là cách tiếp cận bạo lực trong C++. Nó không cắt giảm hoán vị tương đương, ví dụ: cho 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

Được rồi, có cách tiếp cận vũ lực mạnh mẽ với việc cắt tỉa. Này có O (N^3)

Để dễ trình diễn, tôi sẽ đi qua một hình vuông N-by-N có tổng một và b

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

Và tôi tìm cách xây dựng c = {6,7,8}
Tôi tìm thấy '6' trong S. Tôi gỡ bỏ nó, và đánh dấu hàng và cột của nó như là không có sẵn

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

Solution = { (1,5) } 

Sau đó, tôi cố gắng tìm một '7'

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

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

Và cuối cùng là '6'

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

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

The 1st vòng lặp (một cho '6') sẽ tiếp tục và tìm một trận đấu khác: (2,4). Điều này sau đó sẽ tạo thành giải pháp thứ hai {(2,4) (1,6) (3,5)}

Bây giờ, một cách để cải thiện điều này là sử dụng một số chương trình động: tìm tất cả các kết hợp có thể cung cấp kết quả trước.

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) } 

Và bây giờ, các thuật toán tương tự với chẩn đoán nhất định sẽ chạy trong thời gian O (S_l1 * S_l2 * ... S_lN), nơi S_li biểu thị chiều dài của S_i.

Điều này có thể chạy hệ số nhanh hơn trong trường hợp trung bình. Nó cũng sẽ xử lý trường hợp c = {7.7,7} đúng cách.

Đó là tất cả những gì tôi có.