Permutation Group - Transpositions, Simple Transpositions, Inversions and Sorting

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:

    School divides life into two segments, which are increasingly of comparable length. As much as anything else, schooling implies custodial care for persons who are declared undesirable elsewhere by the simple fact that a school has been built to serve them.
    Ivan Illich (b. 1926)