Inversion (discrete mathematics): Difference between revisions

Revision as of 23:12, 24 January 2017

Latest revision as of 21:04, 16 July 2025

(59 intermediate revisions by 29 users not shown)

Line 1:

{{Short description|Pair of positions in a sequence where two elements are out of sorted order}}

[[File:Inversion qtl1.svg|thumb|Permutation with one of is inversions highlighted<br><br>It may be denoted by the pair or places (2, 4) or the pair of elements (5, 2).]]

[[File:Inversion qtl1.svg|thumb|Permutation with one of its inversions highlighted.

In [[computer science]] and [[discrete mathematics]] a sequence has an '''inversion''' where two of its elements are out of their natural [[total order|order]].

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 element-based notation are: (3, 1), (3, 2), (5, 1), (5, 2), and (5,4).]]

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]].

== Definitions ==

Line 6 ⟶ 9:

===Inversion===

Let <math>\pi</math> be a [[permutation]].

Let <math>\pi</math> be a [[permutation]]. If <math>i < j</math> and <math>\pi(i) > \pi(j)</math>, either the pair of places <math>(i, j)</math>{{sfn|Aigner|2007|pp=27}}{{sfn|Comtet|1974|pp=237}} or the pair of elements <math>\bigl(\pi(i), \pi(j)\bigr)</math>{{sfn|Knuth|1973|pp=11}}{{sfn|Pemmaraju|Skiena|2003|pp=69}}{{sfn|Vitter|Flajolet|1990|pp=459}} is called an '''inversion''' of <math>\pi</math>.

There is an '''inversion''' of <math>\pi</math> between <math>i</math> and <math>j</math> if <math>i < j</math> and <math>\pi(i) > \pi(j)</math>. The inversion is indicated by an ordered pair containing either the places <math>(i, j)</math>{{sfn|Aigner|2007|pp=27}}{{sfn|Comtet|1974|pp=237}} or the elements <math>\bigl(\pi(i), \pi(j)\bigr)</math>.{{sfn|Knuth|1973|pp=11}}{{sfn|Pemmaraju|Skiena|2003|pp=69}}{{sfn|Vitter|Flajolet|1990|pp=459}}

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

Inversions are 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.

For sequences, inversions according to the element-based definition are not unique, because different pairs of places may have the same pair of values.

The '''inversion set''' is the set of all inversions. A permutation's inversion set according to the place-based definition is that of the [[Permutation#Product and inverse|inverse]] permutation's inversion set according to the element-based definition, and vice versa,{{sfn|Gratzer|2016|pp=221}} just with the elements of the pairs exchanged.

===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 the sortedness (sometimes called 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, when <math>n = 2m</math> is even, <math>\mathtt{inv}(\langle m+1,m+2,\dots,2m,1,2,\dots, m\rangle)=m^2</math> (because 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.

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.

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.

It does not matter if the place-based or the element-based definition of inversion is used to define the inversion number, because a permutation and its inverse have the same number of inversions.

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

Line 29 ⟶ 32:

Three similar vectors are in use that condense the inversions of a permutation into a vector that uniquely determines it. They are often called ''inversion vector'' or ''[[Lehmer code]]''. (A list of sources is found [[v:Inversion (discrete mathematics)#Sources|here]].)

This article uses the term ''inversion vector'' (<math>v</math>) like [[Wolfram Mathematica|Wolfram]].<ref>{{MathWorldWeisstein, |title=Eric W. [http://mathworld.wolfram.com/InversionVector.html "Inversion Vector}}"] From [[MathWorld]]--A Wolfram Web Resource</ref> The remaining two vectors are sometimes called ''left'' and ''right inversion vector'', but to avoid confusion with the inversion vector this article calls them ''left inversion count'' (<math>l</math>) and ''right inversion count'' (<math>r</math>). Interpreted as a [[factorial number system|factorial number]] the left inversion count gives the permutations reverse colexicographic,<ref>Reverse colex order of finitary permutations {{OEIS|A055089}}</ref> and the right inversion count gives the lexicographic index.

[[File:Inversion example; Rothe 1.svg|thumb|Rothe diagram]]

'''Inversion vector <math>v</math>:'''<br>With the ''element-based'' definition <math>v(i)</math> is the number of inversions whose ''smaller'' (right) component is <math>i</math>.{{sfn|Knuth|1973|pp=11}}

With the ''element-based'' definition <math>v(i)</math> is the number of inversions whose ''smaller'' (right) component is <math>i</math>.{{sfn|Knuth|1973|pp=11}}

:<math>v(i)</math> is the number of elements in <math>\pi</math> greater than <math>i</math> before <math>i</math>.

:<math>v(i) ~~=~~ \# \{ k \mid k > i ~\andland~ \pi^{-1}(k) < \pi^{-1}(i) \}</math>

'''Left inversion count <math>l</math>:'''<br>With the ''place-based'' definition <math>l(i)</math> is the number of inversions whose ''bigger'' (right) component is <math>i</math>.

With the ''place-based'' definition <math>l(i)</math> is the number of inversions whose ''bigger'' (right) component is <math>i</math>.

:<math>l(i)</math> is the number of elements in <math>\pi</math> greater than <math>\pi(i)</math> before <math>\pi(i)</math>.

:<math>l(i) ~~=~~ \# \left\{ k \mid k < i ~\andland~ \pi(k) > \pi(i) \right\}</math>

'''Right inversion count <math>r</math>, often called ''[[Lehmer code]]'':'''<br>With the ''place-based'' definition <math>r(i)</math> is the number of inversions whose ''smaller'' (left) component is <math>i</math>.

With the ''place-based'' definition <math>r(i)</math> is the number of inversions whose ''smaller'' (left) component is <math>i</math>.

:<math>r(i)</math> is the number of elements in <math>\pi</math> smaller than <math>\pi(i)</math> after <math>\pi(i)</math>.

:<math>r(i) ~~=~~ \# \{ k \mid k > i ~\andland~ \pi(k) < \pi(i) \}</math>

Both <math>v</math> and <math>r</math> can be found with the help of a '''[[Rothe diagram''']], which is a [[permutation matrix]] with the 1s represented by dots, and an inversion (often represented by a cross) in every position that has a dot to the right and below it. <math>r(i)</math> is the sum of inversions in row <math>i</math> of the Rothe diagram, while <math>v(i)</math> is the sum of inversions in column <math>i</math>. The permutation matrix of the inverse is the transpose, therefore <math>v</math> of a permutation is <math>r</math> of its inverse, and vice versa.

==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 small columns with smaller print and no heading are reflections of the columns next to them, and can be used to sort them in [[colexicographic order]].)

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 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.)

The default order of the table is reverse colex order by <math>\pi</math>, which is the same as colex order by <math>l</math>. Lex order by <math>\pi</math> is the same as lex order by <math>r</math>.

Line 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.

If a permutation were assigned to each inversion set using the element-based definition, the resulting order of permutations would be that of a [[Cayley graph]], where an edge corresponds to the swapping of two elements on consecutive places. This Cayley graph of the symmetric group is similar to its permutohedron, but with each permutation replaced by its inverse.

==In computer science==

In computer science, it may be useful to calculate the total number of inversions of a permutation. A way to do it is by using a modified version of the [[merge sort]] algorithm. For example, using a modified version of its [[Merge_sort#Top-down_implementation|top-down recursive implementation]]:

<source lang="C">

// Array A[] has the items to sort; array B[] is a work array.

TopDownMergeSort(A[], B[], n)

{

CopyArray(A, 0, n, B); // duplicate array A[] into B[]

TopDownSplitMerge(B, 0, n, A); // sort data from B[] into A[]

}

// Sort the given run of array A[] using array B[] as a source.

// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).

int TopDownSplitMerge(B[], iBegin, iEnd, A[])

{

int inversions=0;

if(iEnd - iBegin < 2) // if run size == 1

return; // consider it sorted

// split the run longer than 1 item into halves

iMiddle = (iEnd + iBegin) / 2; // iMiddle = mid point

// recursively sort both runs from array A[] into B[]

inversions+=TopDownSplitMerge(A, iBegin, iMiddle, B); // sort the left run

inversions+=TopDownSplitMerge(A, iMiddle, iEnd, B); // sort the right run

// merge the resulting runs from array B[] into A[]

inversions+=TopDownMerge(B, iBegin, iMiddle, iEnd, A);

return inversions;

}

// Left source half is A[ iBegin:iMiddle-1].

// Right source half is A[iMiddle:iEnd-1 ].

// Result is B[ iBegin:iEnd-1 ].

int TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])

{

i = iBegin, j = iMiddle;

// While there are elements in the left or right runs...

for (k = iBegin; k < iEnd; k++) {

// If left run head exists and is <= existing right run head.

if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {

B[k] = A[i];

i = i + 1;

} else {

inversions++;

B[k] = A[j];

j = j + 1;

}

}

return inversions;

}

CopyArray(A[], iBegin, iEnd, B[])

{

for(k = iBegin; k < iEnd; k++)

B[k] = A[k];

}

</source>

== See also ==

{{wikiversity|Inversion (discrete mathematics)}}

{{Commons category|Inversion (discrete mathematics)}}

* [[Factorial number system]]

* [[Permutation graph]]

* [[Permutation group#Transpositions, simple transpositions, inversions and sorting|Transpositions, simple transpositions, inversions and sorting]]

* [[Damerau–Levenshtein distance]]

* [[Parity of a permutation]]

Line 151 ⟶ 90:

* Inversion sets of finite permutations interpreted as binary numbers: {{OEIS link|A211362}} &nbsp; (related permutation: {{OEIS link|A211363}})

* Finite permutations that have only 0s and 1s in their inversion vectors: {{OEIS link|A059590}} &nbsp; (their inversion sets: {{OEIS link|A211364}})

* NumbersNumber of permutations of ''n'' elements with ''k'' inversions; Mahonian numbers: {{OEIS link|A008302}} &nbsp; (their row maxima; Kendall-Mann numbers: {{OEIS link|A000140}})

* Number of connected labeled graphs with ''n'' edges and ''n'' nodes: {{OEIS link|A057500}}

Line 158 ⟶ 97:

=== Source bibliography ===

{{refbegin|1}}

* {{cite book | ref = harv

| last = Aigner | first = Martin

| title = A course in enumeration

| chapter = Word Representation

| publisher = Springer | ___location = Berlin, New York | year = 2007 | isbn = 3642072534978-3642072536}}

* {{cite journal

* {{cite journal |ref = harv

| first1 = Wilhelm | last1 = Barth

| first2 = Petra | last2 = Mutzel |author2-link = Petra Mutzel

| title = Simple and Efficient Bilayer Cross Counting

| journal = [[Journal of Graph Algorithms and Applications]] | volume = 8 | issue = 2 | pages = 179&ndash;194 | year = 2004 | doi = 10.7155/jgaa.00088| doi-access = free }}

* {{cite book

* {{cite book |ref = harv

| last = Bóna | first = Miklós | author-link = Miklós Bóna

| title = Combinatorics of permutations

| chapter = 2.2 Inversions in Permutations of Multisets

| publisher = CRC Press | ___location = Boca Raton, FL | year = 2012 | isbn = 1439850518978-1439850510 }}

* {{cite book

* {{cite book |ref = harv

| last = Comtet | first = Louis

| title = Advanced combinatorics; the art of finite and infinite expansions

|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

* {{cite book | ref = harv

| first1=Thomas H. |last1=Cormen |authorlink1=Thomas H. Cormen

| last2=Leiserson |first2=Charles E. |authorlink2=Charles E. Leiserson

Line 195 ⟶ 131:

| edition = 2nd

}}

* {{cite book

* {{cite book | ref = harv

| last = Gratzer | first = George | authorlink = George Grätzer

| title = Lattice theory. special topics and applications

| chapter = 7-2 Basic objects

| publisher = Birkhäuser | ___location = Cham, Switzerland | year = 2016 | isbn = 331944235X978-3319442358 }}

* {{cite book

|last1=Kleinberg|first1=Jon

* {{cite book | ref = harv

|last2=Tardos|first2=Éva

|title=Algorithm Design

|year=2005

|publisher=Pearson/Addison-Wesley

|isbn=0-321-29535-8 }}

* {{cite book

| last1 = Knuth | first1 = Donald

| title = [[The artArt of computerComputer programmingProgramming]]

| chapter = 5.1.1 Inversions

| publisher = Addison-Wesley Pub. Co | year = 1973 | isbn = 0201896850}}

* {{cite book

* {{cite book |ref=harv

|title=Sorting: a distribution theory

|chapter=Sorting Nonrandom Data

Line 215 ⟶ 155:

|first=Hosam Mahmoud |last=Mahmoud

|publisher=Wiley-IEEE |year=2000 |isbn=978-0-471-32710-3}}

* {{cite book

* {{cite book |ref=harv

|title=Computational discrete mathematics: combinatorics and graph theory with Mathematica

|chapter=Permutations and combinations

Line 222 ⟶ 161:

|first2=Steven S.|last2=Skiena

|publisher=Cambridge University Press |year=2003 |isbn=978-0-521-80686-2}}

* {{cite book

* {{cite book |ref=harv

|title=Algorithms and Complexity

|volume=1

Line 237 ⟶ 175:

=== Further reading ===

{{refbegin}}

* {{cite journal|ref=harv|journal=Journal of Integer Sequences|volume=4|year=2001|title=Permutations with Inversions|first=Barbara H.|last=Margolius}}

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

=== Presortedness measures ===

{{refbegin}}

* {{cite journal|ref=harv|journal=Lecture Notes in Computer Science|year=1984|volume=172|pages=324&ndash;336|doi=10.1007/3-540-13345-3_29|title=Measures of presortedness and optimal sorting algorithms|first=Heikki|last=Mannila|authorlink=Heikki Mannila}}

*{{cite journal

* {{cite journal|ref=harv|first1=Vladimir|last1=Estivill-Castro|first2=Derick|last2=Wood|title=A new measure of presortedness|journal=Information and Computation|volume=83|issue=1|pages=111&ndash;119|year=1989|doi=10.1016/0890-5401(89)90050-3}}

| last = Mannila | first = Heikki | author-link = Heikki Mannila

* {{cite journal|ref=harv|first=Steven S.|last=Skiena|year=1988|title=Encroaching lists as a measure of presortedness|journal=BIT|volume=28|issue=4|pages=755&ndash;784|doi=10.1007/bf01954897}}

| date = April 1985

| doi = 10.1109/tc.1985.5009382

| issue = 4

| journal = IEEE Transactions on Computers

| pages = 318–325

| title = Measures of presortedness and optimal sorting algorithms

| volume = C-34}}

* {{cite journal|first1=Vladimir|last1=Estivill-Castro|first2=Derick|last2=Wood|author2-link=Derick Wood|title=A new measure of presortedness|journal=Information and Computation|volume=83|issue=1|pages=111&ndash;119|year=1989|doi=10.1016/0890-5401(89)90050-3|doi-access=free}}

* {{cite journal|first=Steven S.|last=Skiena|year=1988|title=Encroaching lists as a measure of presortedness|journal=BIT|volume=28|issue=4|pages=755&ndash;784|doi=10.1007/bf01954897|s2cid=33967672}}

{{refend}}

[[Category:Permutations]]

[[Category:Order theory]]

[[Category:String similarity measuresmetrics]]

[[Category:Sorting algorithms]]

[[Category:Combinatorics]]