algorithm - 不重复地计算来自多个列表的成对项目的组合

Question

假设我们有多个项目对列表，例如:

1. {12,13,14,23,24}
2. {14,15,25}
3. {16,17,25,26,36}

其中 12 是一对项目“1”和“2”(因此 21 等于 12)，我们想要计算从每个列表中选择项目对的方式的数量，使得没有单个 项目重复。您必须从每个列表中选择一个，并且只能选择一对。每个列表中的项目数和列表数是任意的，但您可以假设至少有两个列表，每个列表至少有一对项目。这些对由有限字母表中的符号组成，假设数字为 [1-9]。此外，列表既不能包含重复对 {12,12} 或 {12,21}，也不能包含对称对 {11}。

更具体地说，在上面的示例中，如果我们从第一个列表中选择项目对 14，那么我们对第二个列表的唯一选择是 25，因为 14 和 15 包含一个“1”。因此，第三个列表中的唯一选择是 36，因为 16 和 17 包含一个“1”，而 25 和 26 包含一个“2”。

有没有人知道一种有效的方法来计算项目对的总组合，而无需遍历每一个选择排列并询问“这是一个有效的选择吗？”，因为每个列表都可以包含数百对元素？

---

更新

在花了一些时间之后，我意识到当没有列表共享不同的对时，计算组合的数量是微不足道的。但是，一旦在两个或多个列表之间共享一个不同的对，组合公式就不适用了。

截至目前，我一直在尝试找出是否有一种方法(使用组合数学而不是蛮力)来计算每个列表具有相同项目对的组合数。例如:

1. {12,23,34,45,67}
2. {12,23,34,45,67}
3. {12,23,34,45,67}

Answer 1

问题是#P-complete。这甚至比 NP-complete 更难。这就像找到 SAT 实例的令人满意的作业数量一样困难。

减少来自Perfect matching .假设您有图 G = {V, E}，其中 E 是边的集合，是顶点对的列表(那些由边连接的顶点对).然后通过具有 E 的 |V|/2 副本对“项目对”的实例进行编码。换句话说，E 的副本数等于顶点数的一半。现在，您的情况下的“命中”将对应于没有重复顶点的 |V|/2 边，这意味着所有 |V| 顶点都被覆盖了。这是完美匹配的定义。每一次完美匹配都会成功——这是 1-1 的对应关系。