HOME

TheInfoList




In
computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of computation, automation, a ...
and
discrete mathematics Discrete mathematics is the study of mathematical structures that are fundamentally discrete space, discrete rather than continuous function, continuous. In contrast to real numbers that have the property of varying "smoothly", the objects stud ...
, an inversion in a sequence is a pair of elements that are out of their natural
order Order, ORDER or Orders may refer to: * Orderliness Orderliness is a quality that is characterized by a person’s interest in keeping their surroundings and themselves well organized, and is associated with other qualities such as cleanliness a ...
.


Definitions


Inversion

Let \pi be a
permutation In , a permutation of a is, loosely speaking, an arrangement of its members into a or , or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order o ...

permutation
. If i < j and \pi(i) > \pi(j), either the pair of places (i, j) or the pair of elements \bigl(\pi(i), \pi(j)\bigr) is called an inversion of \pi. The inversion is usually defined for permutations, but may also be defined for sequences:
Let S be a
sequence In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

sequence
(or
multiset In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
permutation). If i < j and S(i) > S(j), either the pair of places (i, j) or the pair of elements \bigl(S(i), S(j)\bigr) is called an inversion of S. 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
inverse Inverse or invert may refer to: Science and mathematics * Inverse (logic), a type of conditional sentence which is an immediate inference made from another conditional sentence * Additive inverse (negation), the inverse of a number that, when add ...
permutation's inversion set according to the element-based definition, and vice versa, just with the elements of the pairs exchanged.


Inversion number

The inversion number \mathtt(X) of a sequence X=\langle x_1,\dots,x_n\rangle, is the
cardinality In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
of inversion set. It is a common measures of (pre-)sortedness of a permutation or sequence. This value is comprised between 0 and \frac2 included. For example \mathtt(\langle1,2,\dots, n\rangle)=0 since the sequence is ordered. Also \mathtt(\langle n+1,n+2,\dots,2n,1,2,\dots, n\rangle)=n^2 as each pairs (1\le i\le n < j\le 2n) is an inversion. This last example shows that a sort 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, its 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. Standard
comparison sort upright=1.1, Sorting a set of unlabelled weights by weight using only a balance scale requires a comparison sort algorithm. A comparison sort is a type of sorting algorithm In computer science, a sorting algorithm is an algorithm that puts elements ...
ing algorithms can be adapted to compute the inversion number in time .


Inversion related vectors

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 codeIn mathematics and in particular in combinatorics, the Lehmer code is a particular way to encoding, encode each possible permutation of a sequence of ''n'' numbers. It is an instance of a scheme for Permutation#Numbering permutations, numbering permu ...
''. (A list of sources is found
here Here is an adverb that means "in, on, or at this place". It may also refer to: Software * Here Technologies Here Technologies (trading as A trade name, trading name, or business name is a pseudonym A pseudonym () or alias () (originally: ...

here
.) This article uses the term ''inversion vector'' (v) like Wolfram. 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'' (l) and ''right inversion count'' (r). Interpreted as a factorial number the left inversion count gives the permutations reverse colexicographic,Reverse colex order of finitary permutations and the right inversion count gives the lexicographic index. Inversion vector v:
With the ''element-based'' definition v(i) is the number of inversions whose ''smaller'' (right) component is i. :v(i) is the number of elements in \pi greater than i before i. :v(i) ~~=~~ \# \ Left inversion count l:
With the ''place-based'' definition l(i) is the number of inversions whose ''bigger'' (right) component is i. :l(i) is the number of elements in \pi greater than \pi(i) before \pi(i). :l(i) ~~=~~ \# \left\ Right inversion count r, often called ''
Lehmer codeIn mathematics and in particular in combinatorics, the Lehmer code is a particular way to encoding, encode each possible permutation of a sequence of ''n'' numbers. It is an instance of a scheme for Permutation#Numbering permutations, numbering permu ...
'':
With the ''place-based'' definition r(i) is the number of inversions whose ''smaller'' (left) component is i. :r(i) is the number of elements in \pi smaller than \pi(i) after \pi(i). :r(i) ~~=~~ \# \ Both v and r 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. r(i) is the sum of inversions in row i of the Rothe diagram, while v(i) is the sum of inversions in column i. The permutation matrix of the inverse is the transpose, therefore v of a permutation is r of its inverse, and vice versa.


Example: All permutations of four elements

The following sortable table shows the 24 permutations of four elements with their place-based inversion sets, inversion related vectors and inversion numbers. (The small columns are reflections of the columns next to them, and can be used to sort them in colexicographic order.) It can be seen that v and l always have the same digits, and that l and r are both related to the place-based inversion set. The nontrivial elements of l are the sums of the descending diagonals of the shown triangle, and those of r 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.) The default order of the table is reverse colex order by \pi, which is the same as colex order by l. Lex order by \pi is the same as lex order by r.


Weak order of permutations

The set of permutations on ''n'' items can be given the structure of a
partial order In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
, called the weak order of permutations, which forms a lattice. The Hasse diagram of the inversion sets ordered by the
subset In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

subset
relation forms the
skeleton A skeleton is a structural frame that supports an animal Animals (also called Metazoa) are multicellular eukaryotic organisms that form the Kingdom (biology), biological kingdom Animalia. With few exceptions, animals Heterotroph, consu ...
of a
permutohedron In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...

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 on two generators ''a'' and ''b'' In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a Graph (discrete mathematics), graph that encodes the abstract structure of a group (mathemati ...

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.


See also

*
Factorial number system In combinatorics, the factorial number system, also called factoradic, is a mixed radix numeral system adapted to numbering permutations. It is also called factorial base, although factorials do not function as radix, base, but as place value of ...
*
Permutation graphImage:Permutation graph.svg, 300px, Matching diagram for the permutation (4,3,5,1,2), below its corresponding permutation graph In mathematics, a permutation graph is a graph theory, graph whose vertices represent the elements of a permutation, and w ...

Permutation graph
* Transpositions, simple transpositions, inversions and sorting *
Damerau–Levenshtein distanceIn information theory and computer science, the Damerau–Levenshtein distance (named after Frederick J. Damerau and Vladimir Levenshtein, Vladimir I. Levenshtein.) is a string metric for measuring the edit distance between two sequences. Informally, ...
*
Parity of a permutation In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
Sequences in the
OEIS The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while a researcher at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...
:
Sequences related to factorial base representation
* Factorial numbers: and * Inversion numbers: * Inversion sets of finite permutations interpreted as binary numbers:   (related permutation: ) * Finite permutations that have only 0s and 1s in their inversion vectors:   (their inversion sets: ) * Number of permutations of ''n'' elements with ''k'' inversions; Mahonian numbers:   (their row maxima; Kendall-Mann numbers: ) * Number of connected labeled graphs with ''n'' edges and ''n'' nodes:


References


Source bibliography

* * * * * * * * * * *


Further reading

*


Presortedness measures

* * * {{refend Permutations Order theory String metrics Sorting algorithms Combinatorics Discrete mathematics