寻找与给定求和列表对应的一组数对

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

(因为所有的排列本质上是等价的，所以只有一个答案)

我想用长度约为500的列表来实现这个功能，因此朴素的匹配/回溯搜索不可行。

- georgeyiu

---

您想要一组成对序列，其中集合中的每个序列的总和都与序列c匹配？此外，在第一个示例中，[(1,5),(1,6),(2,6)] - 以及许多类似的序列 - 是否也包括在内？ - Ted Hopp

我要解决的问题是每个列表都包含学生的分数。我可以访问每个列表和两个列表的总和，但想知道在给定总分的情况下，可能的子分数是什么。如果这使问题更容易解决（或增加了唯一解的机会），我可以访问N个这些列表，并且可以查询数据库以获取它们的任何子集的总分列表。 - georgeyiu

这个问题在维基百科上被描述为数值三维匹配。它是NP完全问题。 - Evgeny Kluev

第三组为c的负数，且b = 0。好的，谢谢。 - georgeyiu

啊，解决一个非常大的数据集上的NP完全问题。好时光。 - Andrew Mao

什么算是“等价的”？例如，如果 a = [5]*100，b = [10]*100 和 c = [15]*100，是有一个解决方案还是 ~100! 个解决方案？ - nneonneo

Answer 1

好的，这里有一种带修剪的暴力方法。时间复杂度为O(N^3)。

为了方便演示，我将通过一个N×N的正方形，其总和为a和b。

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

我希望构建 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) }

第一个循环（针对“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}的情况。

这基本上就是我所得到的全部内容。

- user1589069

Answer 2

这是一个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;
}

- brooksbp