Content deleted Content added
m Add link to "Permutation matrix". |
→See also: no longer exists |
||
| (22 intermediate revisions by 7 users not shown) | |||
Line 2:
[[File:Inversion qtl1.svg|thumb|Permutation with one of its inversions highlighted.
An inversion may be denoted by the pair of places (2, 4) or the pair of elements (5, 2).
The inversions of this permutation using
In [[computer science]] and [[discrete mathematics]], an '''inversion''' in a sequence is a pair of elements that are out of their natural [[total order|order]].
Line 9:
===Inversion===
Let <math>\pi</math> be a [[permutation]].
The [[#Example:_All_permutations_of_four_elements|inversion set]] is the set of all inversions. A permutation's inversion set using place-based notation is the same as the [[Permutation#Definition|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.{{sfn|Gratzer|2016|pp=221}}
The inversion is usually defined for permutations, but may also be defined for sequences:<br>Let <math>S</math> be a [[sequence]] (or [[multiset]] permutation{{sfn|Bóna|2012|pp=57}}). If <math>i < j</math> and <math>S(i) > S(j)</math>, either the pair of places <math>(i, j)</math>{{sfn|Bóna|2012|pp=57}}{{sfn|Cormen|Leiserson|Rivest|Stein|2001|pp=39}} or the pair of elements <math>\bigl(S(i), S(j)\bigr)</math>{{sfn|Barth|Mutzel|2004|pp=183}} is called an inversion of <math>S</math>.▼
▲
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===
The '''inversion number''' <math>\mathtt{inv}(X)</math>{{sfn|Mannila|1985}} of a sequence <math>X=\langle x_1,\dots,x_n\rangle</math>, is the [[cardinality]] of the inversion set. It is a common
For example <math>\mathtt{inv}(\langle1,2,\dots, n\rangle)=0</math> since the sequence is ordered. Also, <math>\mathtt{inv}(\langle n+1,n+2,\dots,2n,1,2,\dots, n\rangle)=n^2</math> as each pair <math>(1\le i\le n < j\le 2n)</math> is an inversion. This last example shows that a set that is intuitively sorted can still have a quadratic number of inversions.▼
It is the number of crossings in the arrow diagram of the permutation,{{sfn|Gratzer|2016|pp=221}} its [[Kendall tau distance]] from the identity permutation, and the sum of each of the inversion related vectors defined below.▼
▲For example <math>\mathtt{inv}(\langle1,2,\dots, n\rangle)=0</math> since the sequence is ordered. Also, when <math>n = 2m</math> is even, <math>\mathtt{inv}(\langle
▲
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, the Spearman footrule (sum of distances of each element from its sorted position), and the smallest number of exchanges needed to sort the sequence.{{sfn|Mahmoud|2000|pp=284}} Standard [[comparison sort]]ing algorithms can be adapted to compute the inversion number in time {{math|O(''n'' log ''n'')}}.{{sfn|Kleinberg|Tardos|2005|pp=225}}▼
▲Other measures of
===Inversion related vectors===
Line 49 ⟶ 47:
:<math>r(i) ~~=~~ \# \{ k \mid k > i ~\land~ \pi(k) < \pi(i) \}</math>
Both <math>v</math> and <math>r</math> can be found with the help of a
==Example: All permutations of four elements==
[[File:2-element subsets of 4 elements; array, hexagonal.svg|thumb|The six possible inversions of a 4-element permutation]]
The following sortable table shows the 24 permutations of four elements (in the <math>\pi</math> column) with their place-based inversion sets (in the p-b column), inversion related vectors (in the <math>v</math>, <math>l</math>, and <math>r</math> columns), and inversion numbers (in the # column). (The
It can be seen that <math>v</math> and <math>l</math> always have the same digits, and that <math>l</math> and <math>r</math> are both related to the place-based inversion set. The nontrivial elements of <math>l</math> are the sums of the descending diagonals of the shown triangle, and those of <math>r</math> 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.)
Line 73 ⟶ 71:
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 (order)|lattice]].
The [[Hasse diagram]] of the inversion sets ordered by the [[subset]] relation forms the [[skeleton (topology)|skeleton]] of a [[permutohedron]].
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.
Line 81 ⟶ 79:
== See also ==
{{wikiversity|Inversion (discrete mathematics)}}
* [[Factorial number system]]
* [[Permutation graph]]
* [[Damerau–Levenshtein distance]]
* [[Parity of a permutation]]
Line 123 ⟶ 119:
|url = https://archive.org/details/Comtet_Louis_-_Advanced_Coatorics
| chapter = 6.4 Inversions of a permutation of [n]
| publisher = D. Reidel Pub. Co | ___location = Dordrecht, Boston | year = 1974 | isbn = 9027704414 }}
* {{cite book
| first1=Thomas H. |last1=Cormen |authorlink1=Thomas H. Cormen
Line 145 ⟶ 141:
|title=Algorithm Design
|year=2005
|publisher=Pearson/Addison-Wesley
|isbn=0-321-29535-8 }}
* {{cite book
Line 179 ⟶ 176:
=== Further reading ===
{{refbegin}}
* {{cite journal|journal=Journal of Integer Sequences|volume=4|year=2001|title=Permutations with Inversions|first=Barbara H.|last=Margolius|page=24|bibcode=2001JIntS...4...24M}}
{{refend}}
| |||