Given a permutation that maps each i to P(i), Inversion(i) is the number of j < i that appear to the right of i in the permutation. We can thus associate with each permutation, an inversion sequence. An example is given below.
1 2 3 4 5 6 7 8 Permutation P(i) 2 3 1 6 7 8 4 5 Inversion I(i) 0 1 1 0 0 2 2 2
How do we recover the permutation from the inversion sequence?
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky