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:
“Even the simple act that we call “going to visit a person of our acquaintance” is in part an intellectual act. We fill the physical appearance of the person we see with all the notions we have about him, and in the totality of our impressions about him, these notions play the most important role.”
—Marcel Proust (1871–1922)