python - 查找对(连接)的组合

Question

我对 Python 特别感兴趣，但也非常感谢通用解决方案。我有偶数个节点(对于特定示例，假设为 12 个):

['a1', 'a2', 'a3', 'b1', 'b2', 'b3', 'c1', 'c2', 'c3', 'd1', 'd2', 'd3']

每个节点必须连接到另一个节点，形成 6 个连接(对)。我需要找出一种方法来找到所有可能的连接组合。另外，'a1'-'a2'应被视为与 'a2'-'a1' 相同

一些想法:

• 我可以获得可能的列表 itertools.combinations(lst, 2) ，但节点不可重用。比如说，一个连接 'a1'<->'a2'应该消除 'a1'<->'a3'从可用选项中选择为 'a1'已经用过了。

• 我不知道搜索是否适用，因为似乎存在一些问题:

  • 似乎没有(简单、便宜)的方式来跟踪访问过的状态
  • 解决方案永远在底部(需要遍历树所有向下完成所有连接的方式)

Answer 1

这是您问题的递归解决方案:

def findPairs(l):
    # recursion anchor, basic case:
    # when we have 2 nodes only one pair is possible
    if len(l) == 2:
        yield [tuple(l)]
    else:
        # Pair the first node with all the others
        for i in range(1, len(l)):
            # Current pair
            pair1 = [(l[0], l[i])]
            # Combine it with all pairs among the remaining nodes
            remaining = l[1:i] + l[i+1:]
            for otherPairs in findPairs(remaining):
                yield pair1 + otherPairs

据此可以计算出所有解的个数:

def N(n):
    if n == 2:
        return 1
    return (n-1) * N(n-2)

请注意，我没有检查 n % 2 == 0。

此外，对于 n==len(l)==12，您将获得 10395 组可能的组合，这是非常可行的。但是这段代码虽然简短易读，但会一遍又一遍地生成和重新生成列表和元组，这使得它变慢了。
看看它是否足够快，否则我们将不得不对其进行调整。