Permutation Inversion

Each sequence of k distinct elements, with the order of these elements is called a permutation. Consequently, the permutations of k elements differ from each other only in the order of their constituent elements. For example, first six integers can form following permutations:

  1,2,3,4,5,6
  4,6,5,1,3,2
  2,1,6,5,4,3
   . . .
and others.

By definition, two numbers in the permutation is forming inversion when a smaller one is located to the right from the bigger one. Each permutation can match to the number of inversions in it, which is calculated like this: for each of the numbers we determine the amount of its smaller numbers standing to the right, and the results are added together.

For example, let's define the number of inversions in the next permutation: (5,3,1,4,2,6).

Let's solve the task in five steps: let'sdistinguishthefirst (from the left to the right) element and count the number of the elements that are to the right of it, but that are smaller then it. (Let's cross out smaller elements). Then let's process the second element in the same way, etc.

  1)   5,3,1,4,2,6   =>  4
  2)   5,3,1,4,2,6   =>  2
  3)   5,3,1,4,2,6   =>  0
  4)   5,3,1,4,2,6   =>  1
  5)   5,3,1,4,2,6   =>  0

So, the total number of inversions in the permutation is:   4 + 2 + 0 + 1 + 0 = 7

A permutation is called even, if the number of inversions in it is even , and it's called odd otherwise. In particular, the above permutation is odd, as the number of inversions in it is equal to seven.