2
$\begingroup$

Say we are given a congruence relation$~\sim$ in a dataset with $n$ elements. I am looking for an algorithm for optimally sorting the $n$ elements into $m$ clusters according to given congruence relations. For instance if the data contains ${a,b,c,d,e,f,g,h}$, and: $$a\sim b,\ d\sim b,\ e \sim h,\ f \sim c$$ The data should be sorted into the following clusters: $$\{a,b,d\},\ \{c,f\},\ \{e,h\},\ \{g\}$$ As said I'm looking for an efficient algorithm to solve this, I am led to believe this can be done in $O(n)$, but I can't seem to work out the details.

$\endgroup$
2
$\begingroup$

I've always heard this referred to as a "Union Find". It's described here, as well as the optimizations you can do to beat the naive implementation: http://www.algorithmist.com/index.php/Union_Find

$\endgroup$
  • 2
    $\begingroup$ For further reference, a great presentation on the subject can be found here $\endgroup$ – nbubis Feb 19 '13 at 21:26
1
$\begingroup$

Write your relation as a sparse graph and use a "connected components" function, like this.

$\endgroup$

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.