Suppose I have a collection $A$ that I want to partition into equivalence classes, according to some equivalence predicate $E$.
The naive algorithm for doing this is essentially recursive. It consists of picking an arbitrary item $x$ of $A$, using it to "seed" its equivalence class $[x]$, and filling $[x]$ out by iterating over the remaining items $y$ of $A$, adding $y$ to $[x]$ iff $E(x, y)$ is true. Then this base procedure is repeated recursively on the subcollection $A^\prime$ of $A$ consisting of all the items of $A$ that were not assigned to $[x]$.
I would like to know
- the technical name for this generic problem; and
- whether it is possible to do better performance-wise than the naive algorithm described above.