Imagine the following sets :
A = Set( sortedSet(1,2,3), sortedSet(4,8)) B = Set( sortedSet(3,4), sortedSet(5,6,7) )
Where each inner list represent a cluster composed by indexed dots (1,2,3...).
I want to gather cluster sharing the dots sharing the same index into one to get :
Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) )
My first attempt was to merge two Sets
Set( sortedSet(1,2,3) ), sortedSet(3,4), sortedSet(4,8), sortedSet(5,6,7) )
and then merge each subset with subset of the same set where they share a common element. And repeat this process $k$ times with the result set until it doesn't change.
0 : Set( sortedSet(1,2,3,4), sortedSet(3,4,8), sortedSet(5,6,7) ) 1 : Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) ) 2 : Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) ) 1 = 2 then Stop
Unfortunately i think this method is upperbounded in a bit less than $O(k.n^2)$ where n is the total number of elements in every subsets.
My second attempt was to get links which connected subsets of A and B. Add to each A's subsets every sub sets of B which are connected to them from the link A -> B to get A'. Then use link B -> A to gathered A' subsets to get A''. Finally i apply my first attempt on A'' to get A''' and add it the lonely clusters in A and B.
So my final result is A''' + A_lonely + B_lonely
I use optimization that i know like using SortedSet and exist method (rather than go through each subset to know if they share a common element).
The second method works way faster (5min VS 45min) for a precise test. But i know that i can still encounter the same issue due to the step A'' -> A''' which remains quadratic.
Any optimizations i could use or proper solution is welcome !