Inversión (matemáticas)

En informática e matemáticas discretas, unha inversión nunha secuencia é un par de elementos que están fóra da súa orde natural.

Permutación cunha das súas inversións destacada. Unha inversión pódese denotar polo par de lugares (2, 4) ou polo par de elementos (5, 2). As inversións desta permutación mediante a notación baseada en elementos son: (3, 1), (3, 2), (5, 1), (5, 2) e (5,4).

Definicións

Inversión

Sexa $\pi$ unha permutación. Hai unha inversión de $\pi$ entre $i$ e $j$ se $i<j$ e $\pi (i)>\pi (j)$. A inversión indícase mediante un par ordenado que contén calquera dos lugares $(i,j)$ ou os elementos ${\bigl (}\pi (i),\pi (j){\bigr )}$.

O conxunto de inversión é o conxunto de todas as inversións. O conxunto de inversión dunha permutación que usa a notación baseada no lugar é o mesmo que o conxunto de inversión da permutación inversa usando a notación baseada en elementos cos dous compoñentes de cada par ordenado intercambiados. Do mesmo xeito, o conxunto de inversión dunha permutación que usa a notación baseada en elementos é o mesmo que o conxunto de inversión da permutación inversa usando a notación baseada no lugar cos dous compoñentes de cada par ordenado intercambiados.

As inversións adoitan definirse para as permutacións, mais tamén se poden definir para as secuencias:Sexa $S$ unha secuencia, se $i<j$ e $S(i)>S(j)$, ben o par de lugares $(i,j)$ ou o par de elementos ${\bigl (}S(i),S(j){\bigr )}$ chámase inversión de $S$.

Para as secuencias, as inversións segundo a definición baseada en elementos non son únicas, porque diferentes pares de lugares poden ter o mesmo par de valores.

Número da inversión

O número da inversión ${\mathtt {inv}}(X)$ dunha secuencia $X=\langle x_{1},\dots ,x_{n}\rangle$, é a cardinalidade do conxunto de inversión. É unha medida común de ordenación (ás veces chamada preclasificación) dunha permutación ou secuencia. O número de inversión está entre 0 e ${\frac {n(n-1)}{2}}$ inclusive. Unha permutación e a súa inversa teñen o mesmo número de inversión.

Por exemplo ${\mathtt {inv}}(\langle 1,2,\dots ,n\rangle )=0$ xa que a secuencia está ordenada. Ademais, cando $n=2m$ é par, ${\mathtt {inv}}(\langle m+1,m+2,\dots ,2m,1,2,\dots ,m\rangle )=m^{2}$ (porque cada parella $(1\leq i\leq m<j\leq 2m)$ é unha inversión). Este último exemplo mostra que un conxunto intuitivamente "case ordenado" aínda pode ter un número cadrático de inversións.

O número de inversión é o número de cruzamentos no esquema de frecha da permutation,[6] a distancia tau de Kendall da permutación desde a identidade, e a suma de cada un dos vectores de inversión relacionados definidos abaixo.

Outras medidas de ordenación inclúen o número mínimo de elementos que se poden eliminar da secuencia para obter unha secuencia totalmente ordenada, a regra de pé de Spearman (suma das distancias de cada elemento dende a súa posición ordenada), e o menor número de trocos necesarios para ordenar a secuencia. Os algoritmos estándar de ordenación por comparación pódense adaptar para calcular o número de inversión nun tempo O(n log n).

Vectores relacionados coa inversión

Están en uso tres vectores similares que condensan as inversións dunha permutación nun vector que a determina de forma única. Adoitan chamarse vector de inversión ou código de Lehmer. (Atópase aquí unha lista de fontes).

Este artigo usa o termo vector de inversión ($v$) como as páxinas de Wolfram Mathematica. Os dous vectores restantes ás veces chámanse vector de inversión pola esquerda e pola dereita, mais para evitar confusións co vector de inversión, este artigo chámaos conta de inversión pola esquerda ($l$) e conta de inversión pola dereita ($r$). Interpretado como un sistema de numeración factorial, a conta de inversión pola esquerda dá as permutacións colexicográficas inversas, e a conta de inversión pola dereita dá o índice lexicográfico.

Diagrama de Rothe

Vector de inversión $v$:Coa definición baseada en elementos $v(i)$ é o número de inversións cuxo compoñente menor (dereito) é $i$.

$v(i)$ é o número de elementos en $\pi$ máis grande cá $i$ en posición anterior a $i$.

$v(i)~~=~~\#\{k\mid k>i~\land ~\pi ^{-1}(k)<\pi ^{-1}(i)\}$

Conta de inversión pola esquerda $l$ :Coa definición baseada no lugar $l(i)$ é o número de inversións cuxo compoñente (dereito) maior é $i$ .

$l(i)$ é o número de elementos en $\pi$ máis grande cá $\pi (i)$ en posición anterior a $\pi (i)$.

$l(i)~~=~~\#\left\{k\mid k<i~\land ~\pi (k)>\pi (i)\right\}$

Conta de inversións pola dereita $r$, a miúdo chamado código de Lehmer :Coa definición baseada no lugar $r(i)$ é o número de inversións cuxa compoñente menor (esquerda) é $i$ .

$r(i)$ é o número de elementos en $\pi$ menor que $\pi (i)$ posteriores a $\pi (i)$ .

$r(i)~~=~~\#\{k\mid k>i~\land ~\pi (k)<\pi (i)\}$

Ambos os $v$ e $r$ pódense atopar coa axuda dun diagrama de Rothe, que é unha matriz de permutación cos 1 representados por puntos, e unha inversión (a miúdo representada por unha cruz) en cada posición que teña un punto á dereita e debaixo dela. $r(i)$ é a suma das inversións na fila $i$ do diagrama de Rothe, mentres que $v(i)$ é a suma das inversións na columna $i$. A matriz de permutación da inversa é a transposta, polo tanto o $v$ dunha permutación é o $r$ da súa inversa, e viceversa.

Exemplo: todas as permutacións de catro elementos

As seis posibles inversións dunha permutación de 4 elementos

A seguinte táboa ordenada mostra as 24 permutacións de catro elementos (na columna $\pi$) cos seus conxuntos de inversión baseados no lugar (na columna p-b), os vectores relacionados coa inversión (nas columnas $v$, $l$, e $r$) e os números de inversión (na columna #). (As columnas con letra máis pequena e sen título son reflexos das columnas situadas ao lado, e pódense usar para ordenar por orde colexicográfica).

Pódese ver que $v$ e $l$ sempre teñen os mesmos díxitos, e que tano $l$ como $r$ están relacionados co conxunto de inversión baseado no lugar. Os elementos non triviais de $l$ son as sumas das diagonais descendentes do triángulo mostrado e os de $r$ son as sumas das diagonais ascendentes. (Os pares en diagonais descendentes teñen en común as compoñentes dereitas 2, 3, 4, mentres que os pares en diagonais ascendentes teñen en común as compoñentes esquerdas 1, 2, 3).

A orde predeterminada da táboa é a orde "colex" inversa por $\pi$, que é o mesmo que a orde colex por $l$. A orde "lex" por $\pi$ é o mesmo que a orde "lex" por $r$.

Permutacións de 3 elementos para comparación
0 0 1 2 3 4 5 $\pi$ $v$ $l$ p-b $r$ # 0 123 321 000 000 000 000 000 000 0 1 213 312 100 001 010 010 100 001 1 2 132 231 010 010 100 001 010 010 1 3 312 213 110 011 110 011 200 002 2 4 231 132 200 002 200 002 110 011 2 5 321 123 210 012 210 012 210 012 3 11

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

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

Orde feble de permutacións

Permutoedro do grupo simétrico S₄

Ao conxunto de permutacións de n elementos pódeselle dar a estrutura dunha orde parcial, chamada orde feble de permutacións, que forma unha retícula.

O diagrama de Hasse dos conxuntos de inversión ordenados pola relación de subconxuntos forma o esqueleto dun permutoedro.

Se se asignase unha permutación a cada conxunto de inversión usando a definición baseada en elementos, a orde resultante das permutacións sería a dun grafo de Cayley, onde unha aresta corresponde ao troco de dous elementos en lugares consecutivos. Este grafo de Cayley do grupo simétrico é semellante ao seu permutoedro, mais con cada permutación substituída pola súa inversa.

Véxase tamén

Bibliografía

• Aigner, Martin (2007). "Word Representation". A course in enumeration. Berlin, New York: Springer. ISBN 978-3642072536. 
• Barth, Wilhelm; Mutzel, Petra (2004). "Simple and Efficient Bilayer Cross Counting". Journal of Graph Algorithms and Applications 8 (2): 179–194. doi:10.7155/jgaa.00088. 
• Bóna, Miklós (2012). "2.2 Inversions in Permutations of Multisets". Combinatorics of permutations. Boca Raton, FL: CRC Press. ISBN 978-1439850510. 
• 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. 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-53196-8. 
• Gratzer, George (2016). "7-2 Basic objects". Lattice theory. special topics and applications. Cham, Switzerland: Birkhäuser. ISBN 978-3319442358. 
• Kleinberg, Jon; Tardos, Éva (2005). Algorithm Design. ISBN 0-321-29535-8. 
• Knuth, Donald (1973). "5.1.1 Inversions". The Art of Computer Programming. Addison-Wesley Pub. Co. ISBN 0201896850. 
• 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". En van Leeuwen, Jan. Algorithms and Complexity 1 (2nd ed.). Elsevier. ISBN 978-0-444-88071-0. 

Outros artigos

• Paridade dunha permutación.
• Sistema de numeración factorial.
• Permutación.
• Grupo das permutacións.