Transpositions, Simple Transpositions, Inversions and Sorting
A 2-cycle is known as a transposition. A simple transposition in Sn is a 2-cycle of the form (i i + 1).
For a permutation p in Sn, a pair (i, j)∈In is a permutation inversion, if when i<j, we have p(i) > p(j).
Every permutation can be written as a product of simple transpositions; furthermore, the number of simple transpositions one can write a permutation p in Sn can be the number of inversions of p and if the number of inversions in p is odd or even the number of transpositions in p will also be odd or even corresponding to the oddness of p.
Read more about this topic: Permutation Group
Famous quotes containing the word simple:
“What have Massachusetts and the North sent a few sane representatives to Congress for, of late years?... All their speeches put together and boiled down ... do not match for manly directness and force, and for simple truth, the few casual remarks of crazy John Brown on the floor of the Harper’s Ferry engine-house,—that man whom you are about to hang, to send to the other world, though not to represent you there.”
—Henry David Thoreau (1817–1862)