The Mathematica Journal
Departments
Feature Articles
Columns
New Products
New Publications
Classifieds
Calendar
News Bulletins
Mailbox
Letters
Write Us
About the Journal
Staff and Contributors
Submissions
Subscriptions
Advertising
Back Issues
Home
Download this Issue

Preorders

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 [Graphics:../Images/index_gr_28.gif] (the third property of an order, [Graphics:../Images/index_gr_29.gif], may be missing). Call a preorder total, if [Graphics:../Images/index_gr_30.gif] for all [Graphics:../Images/index_gr_31.gif] and [Graphics:../Images/index_gr_32.gif]. Preorders are almost like orders; however, it may happen that [Graphics:../Images/index_gr_33.gif] is less than [Graphics:../Images/index_gr_34.gif] and [Graphics:../Images/index_gr_35.gif] is less than [Graphics:../Images/index_gr_36.gif], without [Graphics:../Images/index_gr_37.gif] being identical to [Graphics:../Images/index_gr_38.gif]. Such a preorder generates an equivalence and it is exactly those problem elements that will be equivalent. The generated equivalence [Graphics:../Images/index_gr_39.gif] is therefore defined this way: [Graphics:../Images/index_gr_40.gif]. 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 [Graphics:../Images/index_gr_41.gif] has the property [Graphics:../Images/index_gr_42.gif] for all [Graphics:../Images/index_gr_43.gif]. If [Graphics:../Images/index_gr_44.gif] 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 OrderedQ[{#1,#2}]&, which we can write more elegantly as Composition[OrderedQ,List].

[Graphics:../Images/index_gr_45.gif]

This method has complexity [Graphics:../Images/index_gr_46.gif], because of sorting. The default predicate is canonical ordering, which leads to the trivial SameQ equivalence. We can use it as the basis of another, faster classification function. This time we implement it directly, without the detour through PreorderIndices.

[Graphics:../Images/index_gr_47.gif]
[Graphics:../Images/index_gr_48.gif]
[Graphics:../Images/index_gr_49.gif]

The computation of a transversal of our sample random integers using the default preorder is already much faster than is the built-in Union function.

[Graphics:../Images/index_gr_50.gif]
[Graphics:../Images/index_gr_51.gif]

One important source of preorders are canonical simplifiers.


Converted by Mathematica      

[Article Index] [Prev Page][Next Page]