确定等价类的算法

Question

相当笼统的问题。我有一个这样的列表:

A B  
A C  
C A   
D E  
F G   
E F  
C L  
M N  

等等。

我想做的是找出所有关系并将相关的所有内容放在一行中。上面的例子会变成:

A B C L   
D E F G  
M N      

这样每个字母只出现一次，并且彼此相关的字母排在一行(列表、数组等)。

这是定义明确的算法的某种已知问题吗？它有名字吗？听起来应该是这样。我假设应该有某种递归解决方案。

Answer 1

解决这个问题的一种方法是使用无向图 G=(V,E)。输入中的每一对代表 E 中的一条边，您想要的输出是 connected components G 的。有一些很棒的 Python 图形模块，例如 NetworkX .

演示

>>> data
[['A', 'B'], ['A', 'C'], ['C', 'A'], ['D', 'E'], ['F', 'G'], ['E', 'F'], ['C', 'L'], ['M', 'N']]
>>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_edges_from( data )
>>> components = nx.connected_components( G )
>>> print "\n".join([ " ".join(sorted(cc)) for cc in components ])
A B C L
D E F G
M N