Inversion (discrete mathematics)
|This article appears to contradict the articles Permutation, Lehmer code and Factorial number system. (March 2013)|
Other measures of (pre-)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, and the smallest number of exchanges needed to sort the sequence. Standard comparison sorting algorithms can be adapted to compute the inversion number in time O(n log n).
The inversion vector V(i) of the sequence is defined for i = 2, ..., n as . In other words each element is the number of elements preceding the element in the original sequence that are greater than it. Note that the inversion vector of a sequence has one less element than the sequence, because of course the number of preceding elements that are greater than the first is always zero. Each permutation of a sequence has a unique inversion vector and it is possible to construct any given permutation of a (fully sorted) sequence from that sequence and the permutation's inversion vector.
Weak order of permutations
To define this order, consider the items being permuted to be the integers from 1 to n, and let Inv(u) denote the set of inversions of a permutation u for the natural ordering on these items. That is, Inv(u) is the set of ordered pairs (i, j) such that 1 ≤ i < j ≤ n and u(i) > u(j). Then, in the weak order, we define u ≤ v whenever Inv(u) ⊆ Inv(v).
The edges of the Hasse diagram of the weak order are given by permutations u and v such that u < v and such that v is obtained from u by interchanging two consecutive values of u. These edges form a Cayley graph for the group of permutations that is isomorphic to the skeleton of a permutohedron.
The identity permutation is the minimum element of the weak order, and the permutation formed by reversing the identity is the maximum element.
|Wikiversity has learning materials about Inversion (discrete mathematics)|
|Wikimedia Commons has media related to Inversion (discrete mathematics).|
- Factorial number system (a factorial number is a reflected inversion vector)
- Transpositions, simple transpositions, inversions and sorting
- Damerau–Levenshtein distance
- Parity of a permutation
Sequences in the OEIS:
- Index entries for sequences related to factorial numbers
- Reflected inversion vectors: A007623 and A108731
- Sum of inversion vectors, cardinality of inversion sets: A034968
- Inversion sets of finite permutations interpreted as binary numbers: A211362 (related permutation: A211363)
- Finite permutations that have only 0s and 1s in their inversion vectors: A059590 (their inversion sets: A211364)
- Numbers of permutations of n elements with k inversions; Mahonian numbers: A008302 (their row maxima; Kendall-Mann numbers: A000140)
- Number of connected labeled graphs with n edges and n nodes: A057500
- Arrays of permutations with similar inversion sets and inversion vectors: A211365, A211366, A211367, A211368, A211369, A100630, A211370, A051683
- Barth, Wilhelm; Mutzel, Petra (2004). "Simple and Efficient Bilayer Cross Counting". Journal of Graph Algorithms and Applications 8 (2): 179–194.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-53196-8.
- Mahmoud, Hosam Mahmoud (2000). "Sorting Nonrandom Data". Sorting: a distribution theory. Wiley-Interscience series in discrete mathematics and optimization 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. Algorithms and Complexity 1 (2nd ed.). Elsevier. ISBN 978-0-444-88071-0.
- Margolius, Barbara H. (2001). "Permutations with Inversions". Journal of Integer Sequences 4.
- Mannila, Heikki (1984). "Measures of presortedness and optimal sorting algorithms". Lecture Notes in Computer Science 172: 324–336. doi:10.1007/3-540-13345-3_29.
- Estivill-Castro, Vladimir; Wood, Derick (1989). "A new measure of presortedness". Information and Computation 83 (1): 111–119.
- Skiena, Steven S. (1988). "Encroaching lists as a measure of presortedness". BIT 28 (4): 755–784.