Inversion (discrete mathematics): Difference between revisions

Revision as of 15:29, 1 October 2022

Revision as of 16:00, 1 October 2022

Line 20:

===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 sortedness (pre-)<wbrsometimes />sortednesscalled presortedness) of a permutation{{sfn|Vitter|Flajolet|1990|pp=459}} or sequence.{{sfn|Barth|Mutzel|2004|pp=183}} The inversion number is between 0 and <math>\frac{n(n-1)}2</math> inclusive. A permutation and its inverse have the same inversion number.

For example <math>\mathtt{inv}(\langle1,2,\dots, n\rangle)=0</math> since the sequence is ordered. Also, for <math>m=n/2</math>, <math>\mathtt{inv}(\langle m+1,m+2,\dots,2m,1,2,\dots, m\rangle)=m^2</math> as each pair <math>(1\le i\le m < j\le 2m)</math> is an inversion. This last example shows that a set that is intuitively "nearly" sorted can still have a quadratic number of inversions.

Line 26:

The inversion number is the number of crossings in the arrow diagram of the permutation,{{sfn|Gratzer|2016|pp=221}} 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 (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===