Inversion (discrete mathematics): Difference between revisions

Revision as of 12:31, 1 October 2022

Revision as of 15:07, 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 presortedness|measures of (pre-)<wbr />sortedness]] 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.