<p>See the paper</p>

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

<p>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).</p>

CC BY-SA 3.0
2015-12-05T02:06:43.223Z
2015-12-05T02:06:43.223Z
David Eppstein
<p>Suppose I have a collection $A$ that I want to partition into equivalence classes, according to some equivalence predicate $E$.</p>

<p>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]$.</p>

<p>I would like to know</p>

<ol>
<li>the technical name for this generic problem; and</li>
<li>whether it is possible to do better performance-wise than the naive algorithm described above.</li>
</ol>

CC BY-SA 3.0
2015-11-30T16:20:56.253Z
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) \}$
Kate F
CC BY-SA 3.0
2015-11-30T17:08:00.223Z
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.
Yonatan N
CC BY-SA 3.0
2015-12-01T14:49:58.667Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-12-01T16:37:10.070Z
... 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).
Yonatan N
<ds.algorithms><terminology>
On partitioning a collection into equivalence classes
kjo
# On partitioning a collection into equivalence classes

(Asked by: username_0 on 2015-11-30)

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.

**Tags:** ds.algorithms, terminology
> **Comments:**
> **username_1**: 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) \}$  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_2**: ... 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).  

---

## 1 answers

### Answer by username_4 on 2015-12-05. Score: 6 | Accepted answer

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](http://doi.org/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).


---

