如何还原N choose 2组合？求更优解法或代码优化方案

问题背景 #

我有一组包含多个N选2组合结果的配对集合，需要将这些组合还原为原始的完整集合。

示例输入 #

inputs = {
    ('id1', 'id2'), ('id1', 'id3'), ('id1', 'id4'),
    ('id2', 'id3'), ('id2', 'id4'),
    ('id3', 'id4'), ('id3', 'id5'),
    ('id4', 'id5'),
    ('id5', 'id6'),
}

示例输出 #

recombinations = [
    ('id1', 'id2', 'id3', 'id4'),
    ('id3', 'id4', 'id5'),
    ('id5', 'id6'),
]

现有暴力实现代码 #

我已经用暴力法实现了功能，代码如下：

import itertools

ids = list(sorted( {i for i in itertools.chain(*inputs)} ))

excludes = set()
recombinations = {tuple(i) for i in map(sorted, inputs)}

for i in range(3, len(ids)+1):
    for subset in itertools.combinations(ids, i):
        for j in range(i-1, len(subset)):
            combs = set(itertools.combinations(subset, j))
            if all(tup in recombinations for tup in combs):
                recombinations.add(subset)
                excludes = excludes.union(combs)

for tup in excludes:
    recombinations.remove(tup)

print(recombinations)

运行结果 #

{('id1', 'id2', 'id3', 'id4'), ('id3', 'id4', 'id5'), ('id5', 'id6')}

优化方案：基于图论的极大团求解 #

暴力法时间复杂度为O(2^n)，元素数量较多时性能极差。实际上这个问题等价于寻找无向图中的所有极大团：每个配对是图的一条边，每个原始完整集合就是一个无法再扩展的完全子图（极大团）。

可以使用Bron–Kerbosch算法高效求解，这是专门用于寻找无向图所有极大团的经典算法，实际运行效率远优于暴力枚举。

优化后代码实现 #

from itertools import combinations

def bronkkerbosch(R, P, X, graph, cliques):
    if not P and not X:
        cliques.add(tuple(sorted(R)))
        return
    for v in list(P):
        bronkkerbosch(R | {v}, P & graph[v], X & graph[v], graph, cliques)
        P.remove(v)
        X.add(v)

def recover_sets(input_pairs):
    # 构建邻接表形式的图
    graph = {}
    for u, v in input_pairs:
        if u not in graph:
            graph[u] = set()
        graph[u].add(v)
        if v not in graph:
            graph[v] = set()
        graph[v].add(u)
    
    # 初始化所有节点集合
    all_nodes = set(graph.keys())
    cliques = set()
    
    # 运行Bron–Kerbosch算法找所有极大团
    bronkkerbosch(set(), all_nodes, set(), graph, cliques)
    
    # 按长度降序、字典序排序，对齐示例输出格式
    return sorted(cliques, key=lambda x: (-len(x), x))

# 测试
inputs = {
    ('id1', 'id2'), ('id1', 'id3'), ('id1', 'id4'),
    ('id2', 'id3'), ('id2', 'id4'),
    ('id3', 'id4'), ('id3', 'id5'),
    ('id4', 'id5'),
    ('id5', 'id6'),
}

recombinations = recover_sets(inputs)
print(recombinations)

运行结果 #

[('id1', 'id2', 'id3', 'id4'), ('id3', 'id4', 'id5'), ('id5', 'id6')]

方案优势 #

• 效率提升：Bron–Kerbosch算法在实际场景中性能远超暴力枚举，节点数量越多优势越明显。
• 逻辑清晰：直接对应问题的图论本质，代码可读性和可维护性更强。
• 结果准确：能精准找出所有极大团，不会出现遗漏或错误。

内容的提问来源于stack exchange，提问作者Fravadona