ExamplesLists under ReversalThis example appeared in the Usenet discussion that motivated this article [1]. The example was formulated in terms of permutations, but it works for arbitrary lists. Two lists are equivalent if they are the same or one is the reverse of the other.
The preorder that generates this equivalence compares the smaller of the lists and its reversal (under canonical ordering).
Here
The canonical simplifier chooses the smaller one of the lists and its reverse.
We generate all permutations of the integers from 1 to 4.
Every equivalence class has two elements.
The canonical transversal consists of all lists with the property that they are smaller than their reversal.
Here, we generate all permutations of the integers from 1 to 6 and measure the timings for the three algorithms.
Lists under PermutationsThis example shows very nicely the power of canonical simplifiers. Two lists are equivalent if they are permutations of each other. It is rather cumbersome to find out whether one list is a permutation of another one. It is much easier to sort both lists and then compare the results. The lists are permutations of each other, if and only if the sorted lists are identical. Here is the equivalence predicate, testing the sorted lists for equality.
The corresponding preorder compares the sorted lists under canonical ordering.
Finally, here is the corresponding canonical simplifier, which is quite straightforward.
Our test example is a list of 2000 lists of four random integers each.
Finally, we find the timings for the three methods.
Converted by Mathematica |