给定一个场景，我们有对项目的多个列表，例如：

{12,13,14,23,24} {14,15,25} {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。

有谁知道的的有效的方法来计算对项目的总组合没有经过选择的每一个排列，问这是一个有效的选择？，因为列表可以分别包含几百双项的？

更新

花一些时间与这之后，我意识到，这是微不足道的计算组合的数目时，没有一个列表共享一个独特的对。然而，一旦作为一个独特的一对两个或两个以上列表之间共享时，组合式不适用。

截至目前，我一直在试图找出是否有一种方法（使用组合数学，而不是蛮力）来计算的组合，其中每个列表都有同样对项目的数量。例如：

{12,23,34,45,67} {12,23,34,45,67} {12,23,34,45,67} 解决方案

现在的问题是＃P-完成。这比NP完全问题就更难了。这是很难，因为找到满意的分配的数量，国家税务总局的一个实例。

的降低是由完美匹配。假设你有图形 G = {V，E} ，其中电子，边集，是名单对顶点（即通过边相连的那些对）。然后连接$ C C项目配对的一个实例$由具有 | V | / 的E 2 复制 。换句话说，有许多电子的一半顶点数量的副本。现在，一个砸在你的案件将对应于 | V | / 2 无重复顶点的边缘，这意味着所有的 | V | 顶点覆盖。这是一个完美匹配的定义。和每一个完美匹配将是一个打击 - 这是一个一一对应

Given a scenario where we have multiple lists of pairs of items, for example:

{12,13,14,23,24} {14,15,25} {16,17,25,26,36}

where 12 is a pair of items '1' and '2' (and thus 21 is equivalent to 12), we want to count the number of ways that we can choose pairs of items from each of the lists such that no single item is repeated. You must select one, and only one pair, from each list. The number of items in each list and the number of lists is arbitrary, but you can assume there are at least two lists with at least one pair of items per list. And the pairs are made from symbols from a finite alphabet, assume digits [1-9]. Also, a list can neither contain duplicate pairs {12,12} or {12,21} nor can it contain symmetric pairs {11}.

More specifically, in the example above, if we choose the pair of items 14 from the first list, then the only choice we have for the second list is 25 because 14 and 15 contain a '1'. And consequently, the only choice from the third list is 36 because 16 and 17 contain a '1', and 25 and 26 contain a '2'.

Does anyone know of an efficient way to count the total combinations of pairs of items without going through every permutation of choices and asking "is this a valid selection?", as the lists can each contain hundreds of pairs of items?

UPDATE

After spending some time with this, I realized that it is trivial to count the number of combinations when none of the lists share a distinct pair. However, as soon as a distinct pair is shared between two or more lists, the combinatorial formula does not apply.

As of now, I've been trying to figure out if there is a way (using combinatorial math and not brute force) to count the number of combinations in which every list has the same pairs of items. For example:

{12,23,34,45,67} {12,23,34,45,67} {12,23,34,45,67}

解决方案

The problem is #P-complete. This is even HARDER than NP-complete. It is as hard as finding the number of satisfying assignments to an instance of SAT.

The reduction is from Perfect matching. Suppose you have the graph G = {V, E} where E, the set of edges, is a list of pairs of vertices (those pairs that are connected by an edge). Then encode an instance of "pairs of items" by having |V|/2 copies of E. In other words, have a number of copies of E equal to half of the number of vertices. Now, a "hit" in your case would correspond to |V|/2 edges with no repeated vertices, implying that all |V| vertices were covered. This is the definition of a perfect matching. And every perfect matching would be a hit -- it's a 1-1 correspondence.