Let be a permutation.
There is an inversion of between and if and . The inversion is indicated by an ordered pair containing either the places [1][2] or the elements .[3][4][5]
The inversion set is the set of all inversions. A permutation's inversion set using place-based notation is the same as the inverse permutation's inversion set using element-based notation with the two components of each ordered pair exchanged. Likewise, a permutation's inversion set using element-based notation is the same as the inverse permutation's inversion set using place-based notation with the two components of each ordered pair exchanged.[6]
Inversions are usually defined for permutations, but may also be defined for sequences: Let be a sequence (or multiset permutation[7]). If and , either the pair of places [7][8] or the pair of elements [9] is called an inversion of .
For sequences, inversions according to the element-based definition are not unique, because different pairs of places may have the same pair of values.
Inversion number
edit
The inversion number[10] of a sequence , is the cardinality of the inversion set. It is a common measure of sortedness (sometimes called presortedness) of a permutation[5] or sequence.[9] The inversion number is between 0 and inclusive. A permutation and its inverse have the same inversion number.
For example since the sequence is ordered. Also, when is even, (because each pair is an inversion). This last example shows that a set that is intuitively "nearly sorted" can still have a quadratic number of inversions.
The inversion number is the number of crossings in the arrow diagram of the permutation,[6] the permutation's Kendall tau distance from the identity permutation, and the sum of each of the inversion related vectors defined below.
Other measures of sortedness include the minimum number of elements that can be deleted from the sequence to yield a fully sorted sequence, the number and lengths of sorted "runs" within the sequence, the Spearman footrule (sum of distances of each element from its sorted position), and the smallest number of exchanges needed to sort the sequence.[11] Standard comparison sorting algorithms can be adapted to compute the inversion number in time O(n log n).[12]
Inversion related vectors
edit
Three similar vectors are in use that condense the inversions of a permutation into a vector that uniquely determines it. They are often called inversion vector or Lehmer code. (A list of sources is found here.)
This article uses the term inversion vector () like Wolfram.[13] The remaining two vectors are sometimes called left and right inversion vector, but to avoid confusion with the inversion vector this article calls them left inversion count () and right inversion count (). Interpreted as a factorial number the left inversion count gives the permutations reverse colexicographic,[14] and the right inversion count gives the lexicographic index.
Inversion vector : With the element-based definition is the number of inversions whose smaller (right) component is .[3]
is the number of elements in greater than before .
Left inversion count : With the place-based definition is the number of inversions whose bigger (right) component is .
is the number of elements in greater than before .
Right inversion count , often called Lehmer code: With the place-based definition is the number of inversions whose smaller (left) component is .
is the number of elements in smaller than after .
Both and can be found with the help of a Rothe diagram, which is a permutation matrix with the 1s represented by dots, and an inversion (often represented by a cross) in every position that has a dot to the right and below it. is the sum of inversions in row of the Rothe diagram, while is the sum of inversions in column . The permutation matrix of the inverse is the transpose, therefore of a permutation is of its inverse, and vice versa.
Example: All permutations of four elements
edit
The following sortable table shows the 24 permutations of four elements (in the column) with their place-based inversion sets (in the p-b column), inversion related vectors (in the , , and columns), and inversion numbers (in the # column). (The columns with smaller print and no heading are reflections of the columns next to them, and can be used to sort them in colexicographic order.)
It can be seen that and always have the same digits, and that and are both related to the place-based inversion set. The nontrivial elements of are the sums of the descending diagonals of the shown triangle, and those of are the sums of the ascending diagonals. (Pairs in descending diagonals have the right components 2, 3, 4 in common, while pairs in ascending diagonals have the left components 1, 2, 3 in common.)
The default order of the table is reverse colex order by , which is the same as colex order by . Lex order by is the same as lex order by .
3-element permutations for comparison
0
1
2
3
4
5
p-b
#
0
123
321
000
000
000
000
000
000
0
1
213
312
100
001
010
010
100
001
1
2
132
231
010
010
100
001
010
010
1
3
312
213
110
011
110
011
200
002
2
4
231
132
200
002
200
002
110
011
2
5
321
123
210
012
210
012
210
012
3
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
p-b
#
0
1234
4321
0000
0000
0000
0000
0000
0000
0
1
2134
4312
1000
0001
0010
0100
1000
0001
1
2
1324
4231
0100
0010
0100
0010
0100
0010
1
3
3124
4213
1100
0011
0110
0110
2000
0002
2
4
2314
4132
2000
0002
0200
0020
1100
0011
2
5
3214
4123
2100
0012
0210
0120
2100
0012
3
6
1243
3421
0010
0100
1000
0001
0010
0100
1
7
2143
3412
1010
0101
1010
0101
1010
0101
2
8
1423
3241
0110
0110
1100
0011
0200
0020
2
9
4123
3214
1110
0111
1110
0111
3000
0003
3
10
2413
3142
2010
0102
1200
0021
1200
0021
3
11
4213
3124
2110
0112
1210
0121
3100
0013
4
12
1342
2431
0200
0020
2000
0002
0110
0110
2
13
3142
2413
1200
0021
2010
0102
2010
0102
3
14
1432
2341
0210
0120
2100
0012
0210
0120
3
15
4132
2314
1210
0121
2110
0112
3010
0103
4
16
3412
2143
2200
0022
2200
0022
2200
0022
4
17
4312
2134
2210
0122
2210
0122
3200
0023
5
18
2341
1432
3000
0003
3000
0003
1110
0111
3
19
3241
1423
3100
0013
3010
0103
2110
0112
4
20
2431
1342
3010
0103
3100
0013
1210
0121
4
21
4231
1324
3110
0113
3110
0113
3110
0113
5
22
3421
1243
3200
0023
3200
0023
2210
0122
5
23
4321
1234
3210
0123
3210
0123
3210
0123
6
Weak order of permutations
edit
The set of permutations on n items can be given the structure of a partial order, called the weak order of permutations, which forms a lattice.
If a permutation is assigned to each inversion set using the place-based definition, the resulting order of permutations is that of the permutohedron, where an edge corresponds to the swapping of two elements with consecutive values. This is the weak order of permutations. The identity is its minimum, and the permutation formed by reversing the identity is its maximum.
If a permutation were assigned to each inversion set using the element-based definition, the resulting order of permutations would be that of a Cayley graph, where an edge corresponds to the swapping of two elements on consecutive places. This Cayley graph of the symmetric group is similar to its permutohedron, but with each permutation replaced by its inverse.
See also
edit
Wikiversity has learning resources about Inversion (discrete mathematics)
Bóna, Miklós (2012). "2.2 Inversions in Permutations of Multisets". Combinatorics of permutations. Boca Raton, FL: CRC Press. ISBN 978-1439850510.
Comtet, Louis (1974). "6.4 Inversions of a permutation of [n]". Advanced combinatorics; the art of finite and infinite expansions. Dordrecht, Boston: D. Reidel Pub. Co. ISBN 9027704414.
Mahmoud, Hosam Mahmoud (2000). "Sorting Nonrandom Data". Sorting: a distribution theory. Wiley-Interscience series in discrete mathematics and optimization. Vol. 54. Wiley-IEEE. ISBN 978-0-471-32710-3.
Pemmaraju, Sriram V.; Skiena, Steven S. (2003). "Permutations and combinations". Computational discrete mathematics: combinatorics and graph theory with Mathematica. Cambridge University Press. ISBN 978-0-521-80686-2.
Vitter, J.S.; Flajolet, Ph. (1990). "Average-Case Analysis of Algorithms and Data Structures". In van Leeuwen, Jan (ed.). Algorithms and Complexity. Vol. 1 (2nd ed.). Elsevier. ISBN 978-0-444-88071-0.
Further reading
edit
Margolius, Barbara H. (2001). "Permutations with Inversions". Journal of Integer Sequences. 4.
Presortedness measures
edit
Mannila, Heikki (April 1985). "Measures of presortedness and optimal sorting algorithms". IEEE Transactions on Computers. C-34 (4): 318–325. doi:10.1109/tc.1985.5009382.
Estivill-Castro, Vladimir; Wood, Derick (1989). "A new measure of presortedness". Information and Computation. 83 (1): 111–119. doi:10.1016/0890-5401(89)90050-3.
Skiena, Steven S. (1988). "Encroaching lists as a measure of presortedness". BIT. 28 (4): 755–784. doi:10.1007/bf01954897. S2CID 33967672.