How to explode set of lists into subsets under criterion?
"Overlapping" is not an equivalence relationship because it is not transitive. So approaches using Gather
and related functions are not possible.
The simplest, though not the most efficient way is to test every pair of elements from the set. After doing that, we can treat this as a ConnectedComponents
problem.
Code:
set = {{a, {1, 2, 3}}, {b, {1}}, {c, {2, 3}}, {d, {4, 5}}, {e, {5}}};
am = Outer[Boole@IntersectingQ[#1[[2]], #2[[2]]] &, set, set, 1]
(* {{1, 1, 1, 0, 0}, {1, 1, 0, 0, 0}, {1, 0, 1, 0, 0}, {0, 0, 0, 1, 1}, {0, 0, 0, 1, 1}} *)
components = ConnectedComponents@AdjacencyGraph[am]
(* {{1, 2, 3}, {4, 5}} *)
Part[set, #] & /@ components
(* {{{a, {1, 2, 3}}, {b, {1}}, {c, {2, 3}}}, {{d, {4, 5}}, {e, {5}}}} *)
Addendum
This is what could happen if we try to use Gather
anyway:
sets = Partition[Range[5], 2, 1]
(* {{1, 2}, {2, 3}, {3, 4}, {4, 5}} *)
Gather[sets, IntersectingQ]
(* { {{1, 2}, {2, 3}},
{{3, 4}, {4, 5}} } *)
ConnectedComponents @ SimpleGraph @ RelationGraph[IntersectingQ @@ {##}[[All, 2]]&, set]
{{{a, {1, 2, 3}}, {b, {1}}, {c, {2, 3}}},
{{d, {4, 5}}, {e, {5}}}}