查找与总和列表对应的对的集合

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