The applet below has two purposes. First, it shows an additional way to visualize a permutation (three other possibilities have been described elsewhere.) The members of the set Nn, i.e., numbers from 1 through n, are arranged on a circle sequentially in a natural order. A permutation
Second, the applet has been written with a certain solution to the Fifteen Puzzle in mind. Specifically, it helps one grasp an assertion about the representation of permutations as a product of disjoint cycles. A single move in the Fifteen puzzle consists in swapping a blank spot with an adjacent tile. The applet shows what happens when a permutation is multiplied by a transposition, i.e. a permutation that swaps two elements and leaves the rest untouched.
(To perform the feat click on the two elements in sequence.)
|What if applet does not run?|
The applet demonstrates an intuitively obvious fact that such an operation changes the number of disjoint cycles in the representation of a permutation by 1. More accurately, swapping elements that belong to the same cycle, splits the cycle into two. Swapping elements that belong to different cycles joins their cycles into one. The operation is equivalent to multiplying the initial permutation on the left by a transposition of the two selected elements.
- Various ways to define a permutation
- Counting and listing all permutations
- Johnson-Trotter Algorithm: Listing All Permutations
Copyright © 1996-2017 Alexander Bogomolny