Inversión (matemáticas discretas)

Permutación con una de sus inversiones resaltada

Se puede denotar por el par de lugares (2, 4) o el par de elementos (5, 2).

En informática y matemáticas discretas , una secuencia tiene una inversión en la que dos de sus elementos están fuera de su orden natural .

Definiciones

Inversión

Sea una permutación . Si y , el par de lugares ^{[1] [2]} o el par de elementos ^{[3] [4] [5]} se llama inversión de .${\displaystyle \pi }$${\displaystyle i<j}$${\displaystyle \pi (i)>\pi (j)}$${\displaystyle (i,j)}$${\displaystyle {\bigl (}\pi (i),\pi (j){\bigr )}}$${\displaystyle \pi }$

La inversión generalmente se define para permutaciones, pero también puede definirse para secuencias:
Sea una secuencia (o permutación multiset ^[6] ). Si y , el par de lugares ^{[6] [7]} o el par de elementos ^[8] se llama inversión de .${\displaystyle S}$${\displaystyle i<j}$${\displaystyle S(i)>S(j)}$${\displaystyle (i,j)}$${\displaystyle {\bigl (}S(i),S(j){\bigr )}}$${\displaystyle S}$

Para las secuencias, las inversiones de acuerdo con la definición basada en elementos no son únicas, porque diferentes pares de lugares pueden tener el mismo par de valores.

El conjunto de inversión es el conjunto de todas las inversiones. El conjunto de inversión de una permutación según la definición basada en el lugar es el del conjunto de inversión de la permutación inversa según la definición basada en elementos, y viceversa, ^[9] sólo con los elementos de los pares intercambiados.

Número de inversión

El número de inversión es la cardinalidad del conjunto de inversión. Es una medida común de la clasificación de una permutación ^[5] o secuencia. ^[8]

Es el número de cruces en el diagrama de flechas de la permutación, ^[9] su distancia tau de Kendall desde la permutación de identidad y la suma de cada uno de los vectores relacionados con la inversión definidos a continuación.

No importa si la definición de inversión basada en lugares o en elementos se utiliza para definir el número de inversión, porque una permutación y su inversa tienen el mismo número de inversiones.

Otras medidas de (pre) ordenación incluyen el número mínimo de elementos que se pueden eliminar de la secuencia para producir una secuencia completamente ordenada, el número y la longitud de las "carreras" ordenadas dentro de la secuencia, la regla de Spearman (suma de distancias de cada elemento desde su posición ordenada), y el menor número de intercambios necesarios para ordenar la secuencia. ^[10] Los algoritmos de clasificación de comparación estándar se pueden adaptar para calcular el número de inversión en el tiempo O ( n log n ) . ^[11]

Vectores relacionados con la inversión

Se utilizan tres vectores similares que condensan las inversiones de una permutación en un vector que la determina de forma única. A menudo se les llama vector de inversión o código de Lehmer . ( Aquí encontrará una lista de fuentes ).

Este artículo utiliza el término vector de inversión ( ) como Wolfram . ^[12] Los dos vectores restantes a veces se denominan vector de inversión izquierdo y derecho , pero para evitar confusiones con el vector de inversión, este artículo los llama recuento de inversión izquierdo ( ) y recuento de inversión derecho ( ). Interpretado como un número factorial, el recuento de inversión de la izquierda da las permutaciones colexicográfico inverso, ^[13] y el recuento de inversión de la derecha da el índice lexicográfico.${\displaystyle v}$${\displaystyle l}$${\displaystyle r}$

Diagrama de Rothe

Vector de inversión :${\displaystyle v}$
con la definición basada en elementos es el número de inversiones cuyo componente más pequeño (derecha) es . ^[3]${\displaystyle v(i)}$${\displaystyle i}$

${\displaystyle v(i)}$es el número de elementos en mayor que antes .${\displaystyle \pi }$${\displaystyle i}$${\displaystyle i}$

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

Recuento de inversiones a la izquierda :${\displaystyle l}$
con la definición basada en el lugar, es el número de inversiones cuyo componente más grande (derecho) es .${\displaystyle l(i)}$${\displaystyle i}$

${\displaystyle l(i)}$es el número de elementos en mayor que antes .${\displaystyle \pi }$${\displaystyle \pi (i)}$${\displaystyle \pi (i)}$

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

Recuento de inversiones a la derecha , a menudo llamado código de Lehmer :${\displaystyle r}$
con la definición basada en el lugar es el número de inversiones cuyo componente más pequeño (izquierdo) es .${\displaystyle r(i)}$${\displaystyle i}$

${\displaystyle r(i)}$es el número de elementos en menor que después .${\displaystyle \pi }$${\displaystyle \pi (i)}$${\displaystyle \pi (i)}$

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

Ambos y se pueden encontrar con la ayuda de un diagrama de Rothe , que es una matriz de permutación con los 1 representados por puntos, y una inversión (a menudo representada por una cruz) en cada posición que tiene un punto a la derecha y debajo. es la suma de las inversiones en la fila del diagrama de Rothe, mientras que es la suma de las inversiones en la columna . La matriz de permutación de la inversa es la transpuesta, por lo tanto de una permutación es de su inversa y viceversa.${\displaystyle v}$${\displaystyle r}$${\displaystyle r(i)}$${\displaystyle i}$${\displaystyle v(i)}$${\displaystyle i}$${\displaystyle v}$${\displaystyle r}$

Ejemplo: todas las permutaciones de cuatro elementos

Las seis posibles inversiones de una permutación de 4 elementos

La siguiente tabla clasificable muestra las 24 permutaciones de cuatro elementos con sus conjuntos de inversión basados ​​en el lugar, vectores relacionados con la inversión y números de inversión. (Las columnas pequeñas son reflejos de las columnas contiguas y se pueden usar para clasificarlas en orden colexicográfico ).

Se puede observar que y siempre tienen los mismos dígitos, y que y están ambos relacionados con el conjunto de la inversión basada en el lugar. Los elementos no triviales de son las sumas de las diagonales descendentes del triángulo mostrado, y los de son las sumas de las diagonales ascendentes. (Los pares en diagonales descendentes tienen los componentes derechos 2, 3, 4 en común, mientras que los pares en diagonales ascendentes tienen los componentes izquierdos 1, 2, 3 en común).${\displaystyle v}$${\displaystyle l}$${\displaystyle l}$${\displaystyle r}$${\displaystyle l}$${\displaystyle r}$

El orden predeterminado de la tabla es el orden colex inverso por , que es el mismo que el orden colex por . Lex order by es el mismo que lex order by .${\displaystyle \pi }$${\displaystyle l}$${\displaystyle \pi }$${\displaystyle r}$

Permutaciones de 3 elementos para comparar
0 1 2 3 4 5 ${\displaystyle \pi }$ ${\displaystyle v}$ ${\displaystyle l}$ pb ${\displaystyle r}$ # 0 123 321 00 0 0 00 00 0 0 00 00 0 0 00 0 1 213 312 10 0 0 01 01 0 0 10 10 0 0 01 1 2 132 231 01 0 0 10 10 0 0 01 01 0 0 10 1 3 312 213 11 0 0 11 11 0 0 11 20 0 0 02 2 4 231 132 20 0 0 02 20 0 0 02 11 0 0 11 2 5 321 123 21 0 0 12 21 0 0 12 21 0 0 12 3

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

${\displaystyle \pi }$ ${\displaystyle v}$ ${\displaystyle l}$ pb ${\displaystyle r}$ # 0 1234 4321 000 0 0 000 000 0 0 000 000 0 0 000 0 1 2134 4312 100 0 0 001 001 0 0 100 100 0 0 001 1 2 1324 4231 010 0 0 010 010 0 0 010 010 0 0 010 1 3 3124 4213 110 0 0 011 011 0 0 110 200 0 0 002 2 4 2314 4132 200 0 0 002 020 0 0 020 110 0 0 011 2 5 3214 4123 210 0 0 012 021 0 0 120 210 0 0 012 3 6 1243 3421 001 0 0 100 100 0 0 001 001 0 0 100 1 7 2143 3412 101 0 0 101 101 0 0 101 101 0 0 101 2 8 1423 3241 011 0 0 110 110 0 0 011 020 0 0 020 2 9 4123 3214 111 0 0 111 111 0 0 111 300 0 0 003 3 10 2413 3142 201 0 0 102 120 0 0 021 120 0 0 021 3 11 4213 3124 211 0 0 112 121 0 0 121 310 0 0 013 4 12 1342 2431 020 0 0 020 200 0 0 002 011 0 0 110 2 13 3142 2413 120 0 0 021 201 0 0 102 201 0 0 102 3 14 1432 2341 021 0 0 120 210 0 0 012 021 0 0 120 3 15 4132 2314 121 0 0 121 211 0 0 112 301 0 0 103 4 dieciséis 3412 2143 220 0 0 022 220 0 0 022 220 0 0 022 4 17 4312 2134 221 0 0 122 221 0 0 122 320 0 0 023 5 18 2341 1432 300 0 0 003 300 0 0 003 111 0 0 111 3 19 3241 1423 310 0 0 013 301 0 0 103 211 0 0 112 4 20 2431 1342 301 0 0 103 310 0 0 013 121 0 0 121 4 21 4231 1324 311 0 0 113 311 0 0 113 311 0 0 113 5 22 3421 1243 320 0 0 023 320 0 0 023 221 0 0 122 5 23 4321 1234 321 0 0 123 321 0 0 123 321 0 0 123 6

Orden débil de permutaciones

Permutoedro del grupo simétrico S ₄

Al conjunto de permutaciones en n elementos se le puede dar la estructura de un orden parcial , llamado orden débil de permutaciones , que forma un retículo .

El diagrama de Hasse de los conjuntos de inversión ordenados por la relación de subconjuntos forma el esqueleto de un permutoedro .

Si se asigna una permutación a cada conjunto de inversión utilizando la definición basada en el lugar, el orden resultante de las permutaciones es el del permutoedro, donde un borde corresponde al intercambio de dos elementos con valores consecutivos. Este es el orden débil de permutaciones. La identidad es su mínimo y la permutación formada al invertir la identidad es su máximo.

Si se asignara una permutación a cada conjunto de inversión utilizando la definición basada en elementos, el orden resultante de las permutaciones sería el de un gráfico de Cayley , donde un borde corresponde al intercambio de dos elementos en lugares consecutivos. Esta gráfica de Cayley del grupo simétrico es similar a su permutoedro, pero con cada permutación reemplazada por su inversa.

Ver también

Wikiversity tiene recursos de aprendizaje sobre inversión (matemáticas discretas)

Wikimedia Commons tiene medios relacionados con Inversión (matemáticas discretas) .

• Sistema de numeración factorial
• Gráfico de permutación
• Transposiciones, transposiciones simples, inversiones y ordenación
• Distancia Damerau-Levenshtein
• Paridad de una permutación

Secuencias en la OEIS :

• Secuencias relacionadas con la representación de base factorial
• Números factoriales: A007623 y A108731
• Números de inversión: A034968
• Conjuntos de inversión de permutaciones finitas interpretadas como números binarios: A211362   (permutación relacionada: A211363 )
• Permutaciones finitas que tienen solo 0 y 1 en sus vectores de inversión: A059590   (sus conjuntos de inversión: A211364 )
• Número de permutaciones de n elementos con k inversiones; Números mahónicos: A008302   (sus máximos de fila; números de Kendall-Mann: A000140 )
• Número de gráficos etiquetados conectados con n bordes y n nodos: A057500

Referencias

1. Aigner 2007 , págs.27.
2. Comtet 1974 , págs.237.
3. Knuth 1973 , págs.11.
4. Pemmaraju y Skiena 2003 , págs.69 .
5. Vitter y Flajolet 1990 , págs.459 .
6. Bóna , 2012 , págs.57 .
7. Cormen y col. 2001 , págs.39.
8. Barth y Mutzel , 2004 , págs.183 .
9. Gratzer , 2016 , págs. 221.
10. Mahmoud 2000 , págs.284.
11. Kleinberg y Tardos 2005 , págs.225.
12. Weisstein, Eric W. "Inversión vector" De MathWorld Recursos Web --A Wolfram
13. Orden colex inverso de permutaciones finitarias (secuencia A055089 en la OEIS )

Bibliografía de origen

• Aigner, Martin (2007). "Representación de palabras". Un curso de enumeración . Berlín, Nueva York: Springer. ISBN 978-3642072536.
• Barth, Wilhelm; Mutzel, Petra (2004). "Conteo cruzado bicapa simple y eficiente" . Revista de algoritmos gráficos y aplicaciones . 8 (2): 179-194. doi : 10.7155 / jgaa.00088 .
• Bóna, Miklós (2012). "2.2 Inversiones en permutaciones de multisets". Combinatoria de permutaciones . Boca Raton, FL: CRC Press. ISBN 978-1439850510.
• Comtet, Louis (1974). "6.4 Inversiones de una permutación de [n]". Combinatoria avanzada; el arte de las expansiones finitas e infinitas . Dordrecht, Boston: D. Reidel Pub. Co. ISBN 9027704414.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-53196-8.
• Gratzer, George (2016). "7-2 Objetos básicos". Teoría de la celosía. temas y aplicaciones especiales . Cham, Suiza: Birkhäuser. ISBN 978-3319442358.
• Kleinberg, Jon; Tardos, Éva (2005). Diseño de algoritmos . ISBN 0-321-29535-8.
• Knuth, Donald (1973). "5.1.1 Inversiones". El arte de la programación informática . Addison-Wesley Pub. Co. ISBN 0201896850.
• Mahmoud, Hosam Mahmoud (2000). "Clasificación de datos no aleatorios". Clasificación: una teoría de la distribución . Serie de Wiley-Interscience en matemáticas discretas y optimización. 54 . Wiley-IEEE. ISBN 978-0-471-32710-3.
• Pemmaraju, Sriram V .; Skiena, Steven S. (2003). "Permutaciones y combinaciones". Matemática discreta computacional: combinatoria y teoría de grafos con Mathematica . Prensa de la Universidad de Cambridge. ISBN 978-0-521-80686-2.
• Vitter, JS; Flajolet, Ph. (1990). "Análisis de casos promedio de algoritmos y estructuras de datos". En van Leeuwen, Jan (ed.). Algoritmos y complejidad . 1 (2ª ed.). Elsevier. ISBN 978-0-444-88071-0.

Lectura adicional

• Margolius, Barbara H. (2001). "Permutaciones con inversiones". Diario de secuencias de enteros . 4 .

Medidas de clasificación previa

• Mannila, Heikki (1984). "Medidas de clasificación previa y algoritmos de clasificación óptimos". Apuntes de conferencias en informática . 172 : 324–336. doi : 10.1007 / 3-540-13345-3_29 . ISBN 978-3-540-13345-2.
• Estivill-Castro, Vladimir; Madera, Derick (1989). "Una nueva medida de clasificación previa" . Información y Computación . 83 (1): 111-119. doi : 10.1016 / 0890-5401 (89) 90050-3 .
• Skiena, Steven S. (1988). "Invasión de listas como medida de clasificación previa". BIT . 28 (4): 755–784. doi : 10.1007 / bf01954897 . S2CID  33967672 .