# Most efficient way to find equivalence classes of an equivalence relation

This is a most basic thing and is probably just built-in but I am ignorant of it, so...

I've got some set S={a,b,c,...} and a function equivalent[x_,y_] returning either True or False (or failing), which is an equivalence relation (that is, reflexive, symmetric and transitive). I would like to subdivide S into classes such that all elements within each class are equivalent in the sense of this function, and no elements from different classes are equivalent.

The only way that came to my mind (and I am actually using it) is most probably awfully inefficient (had to further correct it as pointed out in an answer below):

ConnectedComponents[Graph[Table[p[[1]]<->p[[2]],
{p,Select[Union@Map[Sort,Tuples[S,2]],equivalent@@#&]}]]]


What is the best way to do it?

On request, I am adding a code for (one of) the actual equivalent I need.

I've got a bunch of equal length lists of some linear functions in some variables v[1], ..., v[n], and

equivalent[x_,y_]:=Length[Variables[x]]==Length[Variables[y]]
==Length[Variables[x/.First[Solve[x==(y/.Table[v[k]->freshv[k],{k,n}])]]]]]

• You could e.g. use GatherBy . E.g. Z/Z3 equivalence classes: GatherBy[ Range[20], Mod[#,3]&] gives: {{1, 4, 7, 10, 13, 16, 19}, {2, 5, 8, 11, 14, 17, 20}, {3, 6, 9, 12, 15, 18}} Apr 18, 2021 at 20:15
• @DanielHuber Thanks. Unfortunately I cannot reduce my equivalence relation to a form f[x]==f[y]. Specifically, in my case elements to compare are systems of linear equations, and equivalent means that the solutions of the compound system have the same number of free variables as each of them separately. Apr 18, 2021 at 20:56

Example:

equivalent[x_, y_] := StringLength@x == StringLength@y;

s = ToString /@ {1, 22, 312, 23, 27, 343, 52352};


Solution:

nf = Nearest[s, DistanceFunction -> Boole@*Not@*equivalent];

Reap[FixedPoint[
Complement[#, Replace[#, {x_, y___} :> Sow@nf[x, {All, 1/2}]]] &,
s, Length@s]][[2, 1]]

(*  {{"1"}, {"22", "23", "27"}, {"312", "343"}, {"52352"}}  *)


P.S. A limitation in the OP's approach, which might not be observed in the actual use-case if there are not singleton classes.

ConnectedComponents[
Graph[Table[
p[[1]] <-> p[[2]], {p,
Select[Subsets[s, {2}], equivalent @@ # &]}]]]

(*  {{"23", "22", "27"}, {"343", "312"}}  *)

• Would this work for any ("black box") equivalent? As I said, I only want to use that it is an actual equivalence relation, i. e. equivalent[x,x] is True, equivalent[x,y] gives the same output as equivalent[y,x], and if equivalent[x,y] and equivalent[y,z] both output True, then equivalent[x,z] also outputs True (in particular, singleton classes should not create any problems). Apr 18, 2021 at 21:04
• @მამუკაჯიბლაძე Why wouldn't it work? You should really include a code example in your question, since it is obviously a concern for you. My solution uses only equivalent which returns T/F Apr 18, 2021 at 21:06
• I see, thanks. But you are right, I will add the code. Apr 18, 2021 at 21:07
• Added it. I was worried because my cases seemed more involved than your initial example. As for your last code, you are right, I have a flaw there, will try to repair. Apr 18, 2021 at 21:41

The best I can see is rather similar to your suggestion. For example, with

equivalent[x_, y_] := Mod[x, 7] == Mod[y, 7]


you can use

ConnectedComponents[RelationGraph[equivalent, Range[20]]]
(* {{6, 13, 20}, {5, 12, 19}, {4, 11, 18}, {3, 10, 17}, {2, 9, 16}, {1, 8, 15}, {7, 14}} *)


With this equivalence relationship a simpler form (as suggested by @Daniel Huber) would be

GatherBy[Range[20], Mod[#, 7] &]


but this is not possible for a generic equivalence relation.

• Thanks, this is indeed more concise (and probably more efficient). As for using GatherBy, as I explained in a comment above this is unfortunately not an option in my case - at least I cannot see how to reduce equivalent to such form. Apr 18, 2021 at 20:59