2
$\begingroup$

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

  1. the technical name for this generic problem; and
  2. whether it is possible to do better performance-wise than the naive algorithm described above.
Improve this question
$\endgroup$
4
  • $\begingroup$ Isn't the formal name simply "partitioning"? I think you could define $A$ in terms of $A = A_{\alpha} \cup A_{\beta}$ and then $A_{\alpha} = \{ x,y \in X^2 \mid E(x, y) \}$ $\endgroup$
    – Kate F
    Nov 30, 2015 at 16:20
  • 6
    $\begingroup$ Assuming you don't do double comparisons (both $E(x,y)$ and $E(y,x)$), your algorithm uses $C(n,2)$ comparisons. If there can only be either $n$ or $n-1$ different equivalence classes, there's a trivial lower bound of $C(n,2)$ comparisons to figure out which case you're in (if the first $C(n,2)-1$ comparisons say the elements chosen are unequal). So in some sense your approach is optimal as a function of the number of elements.. A randomized algorithm won't save you anything more than constant factors. $\endgroup$
    – Yonatan N
    Nov 30, 2015 at 17:08
  • 2
    $\begingroup$ This is essentially finding connected components using depth first search. Think of the graph on $A$ where $(x,y)$ is an edge iff $E(x,y)$ is true. $\endgroup$
    – Sasho Nikolov
    Dec 1, 2015 at 14:49
  • 4
    $\begingroup$ ... with the restriction that the graph is a collection of vertex-disjoint cliques. Using that view, my above comment can be viewed as an argument that "has an edge" is an evasive graph property even subject to the collection-of-cliques prior (which is not terribly surprising). $\endgroup$
    – Yonatan N
    Dec 1, 2015 at 16:37

1 Answer 1

Reset to default
6
$\begingroup$

See the paper

Varunkumar Jayapaul, J. Ian Munro, Venkatesh Raman, Srinivasa Rao Satti (2015), "Sorting and Selection with Equality Comparisons", Proc. WADS 2015, LNCS 9214, pp. 434–445, doi:10.1007/978-3-319-21840-3_36

It is exactly about the problem you ask, finding the equivalence classes of an equivalence relation by querying the equivalences of pairs of elements. For an input with $n$ elements and $c$ equivalence classes, the naive algorithm you describe will take time $O(nc)$, but they give a more precise bound for this same algorithm in terms of the sizes of its equivalence classes (Theorem 3) and similarly analyze another algorithm for the same problem that works better when the equivalence classes have unevenly distributed sizes (Theorem 4).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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