Inversion (discrete mathematics)

From Wikipedia, the free encyclopedia
  (Redirected from Weak order of permutations)
Jump to: navigation, search
Permutation with one of is inversions highlighted

It may be denoted by the pair or places (2, 4) or the pair of elements (5, 2).

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

Definitions[edit]

Inversion[edit]

Let be a permutation. If and , either the pair of places [1][2] or the pair of elements [3][4][5] is called an inversion of .

The inversion is usually defined for permutations, but may also be defined for sequences:
Let be a sequence (or multiset permutation[6]). If and , either the pair of places [6][7] or the pair of elements [8] is called an inversion of .

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 permutation's inversion set according to the element-based definition, and vice versa,[9] just with the elements of the pairs exchanged.

Inversion number[edit]

The inversion number is the cardinality of inversion set. It is a common measure of the sortedness of a permutation[5] or sequence.[8]

It is the number of crossings in the arrow diagram of the permutation,[9] 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.[10] Standard comparison sorting algorithms can be adapted to compute the inversion number in time O(n log n).

Inversion related vectors[edit]

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

This article uses the term inversion vector () like Wolfram.[11] 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 () and right inversion count (). Interpreted as a factorial number the left inversion count gives the permutations reverse colexicographic,[12] and the right inversion count gives the lexicographic index.

Rothe diagram

Inversion vector :
With the element-based definition is the number of inversions whose smaller (right) component is .[3]

is the number of elements in greater than before .

Left inversion count :
With the place-based definition is the number of inversions whose bigger (right) component is .

is the number of elements in greater than before .

Right inversion count , often called Lehmer code:
With the place-based definition is the number of inversions whose smaller (left) component is .

is the number of elements in smaller than after .

Both and 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. is the sum of inversions in row of the Rothe diagram, while is the sum of inversions in column . The permutation matrix of the inverse is the transpose, therefore of a permutation is of its inverse, and vice versa.

Example: All permutations of four elements[edit]

The six possible inversions of a 4-element permutation

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 and always have the same digits, and that and are both related to the place-based inversion set. The nontrivial elements of are the sums of the descending diagonals of the shown triangle, and those of 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 , which is the same as colex order by . Lex order by is the same as lex order by .

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
p-b #
0 4-el perm matrix 00.svg 1234 4321 0000 0000 0000 0000 4-el perm invset 00.svg 0000 0000 0
1 4-el perm matrix 01.svg 2134 4312 1000 0001 0010 0100 4-el perm invset 01.svg 1000 0001 1
2 4-el perm matrix 02.svg 1324 4231 0100 0010 0100 0010 4-el perm invset 02.svg 0100 0010 1
3 4-el perm matrix 03.svg 3124 4213 1100 0011 0110 0110 4-el perm invset 03.svg 2000 0002 2
4 4-el perm matrix 04.svg 2314 4132 2000 0002 0200 0020 4-el perm invset 04.svg 1100 0011 2
5 4-el perm matrix 05.svg 3214 4123 2100 0012 0210 0120 4-el perm invset 05.svg 2100 0012 3
6 4-el perm matrix 06.svg 1243 3421 0010 0100 1000 0001 4-el perm invset 06.svg 0010 0100 1
7 4-el perm matrix 07.svg 2143 3412 1010 0101 1010 0101 4-el perm invset 07.svg 1010 0101 2
8 4-el perm matrix 08.svg 1423 3241 0110 0110 1100 0011 4-el perm invset 08.svg 0200 0020 2
9 4-el perm matrix 09.svg 4123 3214 1110 0111 1110 0111 4-el perm invset 09.svg 3000 0003 3
10 4-el perm matrix 10.svg 2413 3142 2010 0102 1200 0021 4-el perm invset 10.svg 1200 0021 3
11 4-el perm matrix 11.svg 4213 3124 2110 0112 1210 0121 4-el perm invset 11.svg 3100 0013 4
12 4-el perm matrix 12.svg 1342 2431 0200 0020 2000 0002 4-el perm invset 12.svg 0110 0110 2
13 4-el perm matrix 13.svg 3142 2413 1200 0021 2010 0102 4-el perm invset 13.svg 2010 0102 3
14 4-el perm matrix 14.svg 1432 2341 0210 0120 2100 0012 4-el perm invset 14.svg 0210 0120 3
15 4-el perm matrix 15.svg 4132 2314 1210 0121 2110 0112 4-el perm invset 15.svg 3010 0103 4
16 4-el perm matrix 16.svg 3412 2143 2200 0022 2200 0022 4-el perm invset 16.svg 2200 0022 4
17 4-el perm matrix 17.svg 4312 2134 2210 0122 2210 0122 4-el perm invset 17.svg 3200 0023 5
18 4-el perm matrix 18.svg 2341 1432 3000 0003 3000 0003 4-el perm invset 18.svg 1110 0111 3
19 4-el perm matrix 19.svg 3241 1423 3100 0013 3010 0103 4-el perm invset 19.svg 2110 0112 4
20 4-el perm matrix 20.svg 2431 1342 3010 0103 3100 0013 4-el perm invset 20.svg 1210 0121 4
21 4-el perm matrix 21.svg 4231 1324 3110 0113 3110 0113 4-el perm invset 21.svg 3110 0113 5
22 4-el perm matrix 22.svg 3421 1243 3200 0023 3200 0023 4-el perm invset 22.svg 2210 0122 5
23 4-el perm matrix 23.svg 4321 1234 3210 0123 3210 0123 4-el perm invset 23.svg 3210 0123 6

Weak order of permutations[edit]

Permutohedron of the symmetric group S4

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.

The Hasse diagram of the inversion sets ordered by the subset relation forms the 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.

See also[edit]

Sequences in the OEIS:

References[edit]

  1. ^ Aigner 2007, pp. 27.
  2. ^ Comtet 1974, pp. 237.
  3. ^ a b Knuth 1973, pp. 11.
  4. ^ Pemmaraju & Skiena 2003, pp. 69.
  5. ^ a b Vitter & Flajolet 1990, pp. 459.
  6. ^ a b Bóna 2012, pp. 57.
  7. ^ Cormen et al. 2001, pp. 39.
  8. ^ a b Barth & Mutzel 2004, pp. 183.
  9. ^ a b Gratzer 2016, pp. 221.
  10. ^ Mahmoud 2000, pp. 284.
  11. ^ Weisstein, Eric W. "Inversion Vector". MathWorld. 
  12. ^ Reverse colex order of finitary permutations (sequence A055089 in the OEIS)

Source bibliography[edit]

  • Aigner, Martin (2007). "Word Representation". A course in enumeration. Berlin, New York: Springer. ISBN 3642072534. 
  • Bóna, Miklós (2012). "2.2 Inversions in Permutations of Multisets". Combinatorics of permutations. Boca Raton, FL: CRC Press. ISBN 1439850518. 
  • Comtet, Louis (1974). "6.4 Inversions of a permutation of [n]". Advanced combinatorics; the art of finite and infinite expansions. Dordrecht,Boston: D. Reidel Pub. Co. ISBN 9027704414. 
  • Gratzer, George (2016). "7-2 Basic objects". Lattice theory. special topics and applications. Cham, Switzerland: Birkhäuser. ISBN 331944235X. 
  • Mahmoud, Hosam Mahmoud (2000). "Sorting Nonrandom Data". Sorting: a distribution theory. Wiley-Interscience series in discrete mathematics and optimization. 54. Wiley-IEEE. ISBN 978-0-471-32710-3. 
  • Pemmaraju, Sriram V.; Skiena, Steven S. (2003). "Permutations and combinations". Computational discrete mathematics: combinatorics and graph theory with Mathematica. Cambridge University Press. ISBN 978-0-521-80686-2. 
  • Vitter, J.S.; Flajolet, Ph. (1990). "Average-Case Analysis of Algorithms and Data Structures". In van Leeuwen, Jan. Algorithms and Complexity. 1 (2nd ed.). Elsevier. ISBN 978-0-444-88071-0. 

Further reading[edit]

  • Margolius, Barbara H. (2001). "Permutations with Inversions". Journal of Integer Sequences. 4. 

Presortedness measures[edit]