python - 在 Python 中处理传递性

Question

我有一组像这样的成对关系

col_combi = [('a','b'), ('b','c'), ('d','e'), ('l','j'), ('c','g'), 
             ('e','m'), ('m','z'), ('z','p'), ('t','k'), ('k', 'n'), 
             ('j','k')]

这种关系的数量足够大，可以单独检查。这些元组表示两个值相同。我想应用传递性并找出共同的群体。输出如下:

[('a','b','c','g'), ('d','e','m','z','p'), ('t','k','n','l','j')]

我试过下面的代码，但它有错误，

common_cols = []
common_group_count = 0

for (c1, c2) in col_combi:
    found = False
    for i in range(len(common_cols)):
        if (c1 in common_cols[i]):
            common_cols[i].append(c2)
            found = True
            break
        elif (c2 in common_cols[i]):
            common_cols[i].append(c1)
            found = True
            break
    if not found:
        common_cols.append([c1,c2])

以上代码的输出如下

[['a', 'b', 'c', 'g'], ['d', 'e', 'm', 'z', 'p'], ['l', 'j', 'k'], ['t', 'k', 'n']]

我知道为什么这段代码不起作用。所以我想知道如何执行此任务。

提前致谢

Answer 1

您可以使用 NetworkX 将此作为图形问题来处理图书馆:

import networkx

col_combi = [('a','b'), ('b','c'), ('d','e'), ('l','j'), ('c','g'), 
             ('e','m'), ('m','z'), ('z','p'), ('t','k'), ('k', 'n'), 
             ('j','k')]

g = networkx.Graph(col_combi)

for subgraph in networkx.connected_component_subgraphs(g):
    print subgraph.nodes()

输出:

['m', 'z', 'e', 'd', 'p']
['t', 'k', 'j', 'l', 'n']
['a', 'c', 'b', 'g']