Поиск множества пар, которые соответствуют списку сумм

Question

Учитывая два списка чисел и список сумм (ни в определенном порядке):

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, поэтому поиск по наивному совпадению/обратному поиску не может быть и речи.

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)

Для удобства демонстрации, я пойду через квадрат N-по-N, который имеет сумму и б

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

и я глядя на сборку c = {6,7,8}
Я нахожу «6» в S. Я удалить его, и отметьте его строку и столбец как недоступный

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.

Этот может ускорить работу в среднем случае. Он также будет обрабатывать дело c = {7,7,7}.

Это почти все, что у меня есть.