处理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')]

我尝试了下面的代码,但它有bug,

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']