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

Examples

Lists under Reversal

This 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.

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

The preorder that generates this equivalence compares the smaller of the lists and its reversal (under canonical ordering).

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

Here min returns the smaller of its two elements (the built-in Min works only for numbers).

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

The canonical simplifier chooses the smaller one of the lists and its reverse.

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

We generate all permutations of the integers from 1 to 4.

[Graphics:../Images/index_gr_79.gif]
[Graphics:../Images/index_gr_80.gif]

Every equivalence class has two elements.

[Graphics:../Images/index_gr_81.gif]
[Graphics:../Images/index_gr_82.gif]
[Graphics:../Images/index_gr_83.gif]
[Graphics:../Images/index_gr_84.gif]
[Graphics:../Images/index_gr_85.gif]
[Graphics:../Images/index_gr_86.gif]
[Graphics:../Images/index_gr_87.gif]
[Graphics:../Images/index_gr_88.gif]
[Graphics:../Images/index_gr_89.gif]
[Graphics:../Images/index_gr_90.gif]
[Graphics:../Images/index_gr_91.gif]
[Graphics:../Images/index_gr_92.gif]
[Graphics:../Images/index_gr_93.gif]

The canonical transversal consists of all lists with the property that they are smaller than their reversal.

[Graphics:../Images/index_gr_94.gif]
[Graphics:../Images/index_gr_95.gif]

Here, we generate all permutations of the integers from 1 to 6 and measure the timings for the three algorithms.

[Graphics:../Images/index_gr_96.gif]
[Graphics:../Images/index_gr_97.gif]
[Graphics:../Images/index_gr_98.gif]

Lists under Permutations

This 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.

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

The corresponding preorder compares the sorted lists under canonical ordering.

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

Finally, here is the corresponding canonical simplifier, which is quite straightforward.

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

Our test example is a list of 2000 lists of four random integers each.

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

Finally, we find the timings for the three methods.

[Graphics:../Images/index_gr_103.gif]
[Graphics:../Images/index_gr_104.gif]


Converted by Mathematica     

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