Algorithm for determining equivalency classes

Question

Rather general question. I have a list like this:

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

and so on.

What I want to do - is to figure out all the relations and put everything that's related in a single line. The example above would become:

A B C L   
D E F G  
M N      

so that every letter appears only once, and the letters that related to each other are on in one line (list, array, whatever).

Is this some kind of known problem with a well-defined algorithm? Does it have a name? Sounds like it should be. I'd assume some kind of a recursive solution should be in place.

Answer 1

One way to solve this is to use an undirected graph G=(V,E). Each pair in your input represents an edge in E, and the output you want is the connected components of G. There are some great Python graph modules such as NetworkX.

Demo

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