An equivalence is a binary relation ~ that is reflexive, symmetric, and transitive. An equivalence class is the set of all elements of the domain of an equivalence relation that are pairwise equivalent.
A preorder is a reflexive and transitive relation (the third property of an order, , may be missing). Call a preorder total, if for all and . Preorders are almost like orders; however, it may happen that is less than and is less than , without being identical to . Such a preorder generates an equivalence and it is exactly those problem elements that will be equivalent. The generated equivalence is therefore defined this way: . Note that a preorder induces a total order on the equivalence classes.
Mathematica's sorting algorithm works also if we specify a total preorder in place of a total order as an ordering predicate. Sorting a list using a total preorder brings equivalent elements into adjacent positions, and the partitioning can then be done in linear time. After sorting, the list has the property for all . If as well, the two elements are equivalent, otherwise they are not; therefore, we can split at the places where this condition is violated.
This procedure takes a preorder as an argument and finds the index partition of the equivalence generated by it. Note how the indices of the elements are tacked onto the elements before sorting, so we know after sorting where the elements were originally. The default ordering predicate is
This method has complexity , because of sorting. The default predicate is canonical ordering, which leads to the trivial
The computation of a transversal of our sample random integers using the default preorder is already much faster than is the built-in
One important source of preorders are canonical simplifiers.
Converted by Mathematica