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:
“And would you be a poet
Before you’ve been to school?
Ah, well! I hardly thought you
So absolute a fool.
First learn to be spasmodic—
A very simple rule.
For first you write a sentence,
And then you chop it small;
Then mix the bits, and sort them out
Just as they chance to fall:
The order of the phrases makes
No difference at all.”
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)