Grouping lists by common elements
algorithm, c++
Solution
For each object, calculate which elements contain it.
i.e.
01 -> [E1, E3]
02 -> [E4]
03 -> [E2, E5]
04 -> [E3]
05 -> [E3, E4]
06 -> [E5]
These lists induce a graph: there's a vertex per element, and two vertices are connected if the corresponding elements show up in the same list.
It seems to me that what you want to calculate are the connected components of the graph.
Problem
I'm looking for a clever/fast C++ algorithm, which would allow me to do grouping of several lists of objects when they contain common objects inside. Let's say I have N lists, each containing 1..M objects (O) associated with one element E: ``` [O1, O2] -> E1 [O3] -> E2 [O1, O4, O5] -> E3 [O2, O5] -> E4 [O3, O6] -> E5 ``` I wish to rearrange them into the following: ``` [O1, O2, O4, O5] -> [E1, E3, E4] [O3, O6] -> [E2, E5] ``` The result has all common objects grouped together with all associated elements. No object is shared in the end between lists.