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 !

  • $\begingroup$ What's a dot? What's an index dot? What's a cluster composed by indexed dots? What is the semantics of Set(x,y) and sortedSet(a,b,c,...)? Are you looking for a Union-Find data structure? It's hard for me to tell what you are looking for. $\endgroup$ – D.W. Aug 16 '17 at 6:16
  • $\begingroup$ Here i don't care about the dot itself, what matters is it's ID that i called index. Yeah thank you after few research on Union-Find data structure i found what i was looking for is Disjoint-set Data Structures. $\endgroup$ – KyBe Aug 16 '17 at 6:24
  • 1
    $\begingroup$ Perhaps you can answer your own question now. $\endgroup$ – D.W. Aug 16 '17 at 6:27
  • $\begingroup$ In fact it is not exactly what i'm looking for because from what i understand from the disjoint-set data structures is that it enable to link set between them through the union function and check if they belong to the same group through find function. But we have to express which group is linked to another and that's precisely this point on which i have difficulties. $\endgroup$ – KyBe Aug 16 '17 at 8:03

You could create an undirected graph which nodes are the clusters from A and B, two clusters being connected if they have a common dot. This graph can be built in time $O(n)$ where $n$ is the number of dots. Then the problem is to find the connected components of this graph. It is a standard problem that has a solution in linear time in terms of the number of edges and vertices of the graph. The clusters from each connected components are then fusioned to create the resulting clusters.

| cite | improve this answer | |

Thank's to @D.W insights, the right way to do this is to use Disjoint-set Data Structures which have a $O(\alpha(n))$ costs to merge where $\alpha$ is the inverse Ackermann function.

Then use them to find connected components in a graph.

| cite | improve this answer | |
  • 1
    $\begingroup$ While it's certainly O(Ackermann), I'm sure that's not what you want to say here. I seem to remember that the inverse Ackermann function plays a role here. Also, data structures do not have "a complexity"; operations on data structures have costs. $\endgroup$ – Raphael Aug 16 '17 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.