Inversion (discrete mathematics): Difference between revisions

Revision as of 20:52, 12 May 2022

Revision as of 10:27, 17 July 2022

Line 17:

===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 [[measure of presortedness|measures of (pre-)sortedness]] of a permutation{{sfn|Vitter|Flajolet|1990|pp=459}} or sequence.{{sfn|Barth|Mutzel|2004|pp=183}} This value is comprised between 0 and <math>\frac{n(n-1)}2</math> included.

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 pairspair <math>(1\le i\le n < j\le 2n)</math> is an inversion. This last example shows that a sortset 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.

Line 26:

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}}

===Inversion related vectors===