Various ways to define a permutation
Permutation of the set Nn is a 1-1 correspondence from Nn onto itself. Let f be such a permutation. The fact that it's onto means that for any
One way to represent a permutation f is by listing its values at
- The upper row appears in its natural order: 1, ..., n. Element f(i) appears directly below i. I call this a straight presentation.
- The upper row appears in its natural order; so does the lower row. Straight lines connect i to f(i).
- The lower row appears in its natural order. The upper row is ordered in such a manner as to have all the links between the elements vertical. This is
a straight upside down presentation. In this case, the upper row is actually
{f -1(1), ..., f -1(n)} and thus presents the inverse permutation of f.
What if applet does not run? |
In the applet, every permutation is also presented as a product of cycles. For every permutation
Write 9. Since a8 = 1, 8 stands to the right of 9. Since
In a table of inversions the last element an is always 0. For there is no element greater than n and, therefore, no element greater than n may be found to the left of n. an-1 may be either 0 or 1 depending on how
Now, every time you press the Reset button the program produces a new permuation. I borrowed an algorithm from [Angel>]. Assume unperturbed set
for (int i = n; i > 1; i--)
{
r = (int)(Math.random()·i);
copy = Value[i];
Value[i] = Value[r];
Value[r] = copy;
}
Remark: there is another auspicious representation of permutations. If all the elements are placed on a circle then arrows may point from an element to its image. An entertaining shuttle puzzle leads to a presentation of permutations as a product of transpositions that are useful in investigating Sam Loyd's Fifteen among others.
Reference
- A. Angel, Exploring Mathematics with Your Computer, MAA, 1993
- D. E. Knuth, The Art of Computer Programming, v3, Addison-Wesley, 1973
Permutations
- Various ways to define a permutation
- Counting and listing all permutations
- Johnson-Trotter Algorithm: Listing All Permutations
|Contact| |Front page| |Contents| |Algebra| |Up|
Copyright © 1996-2018 Alexander Bogomolny
72091455