Inversión (matemáticas discretas)

Par de posiciones en una secuencia donde dos elementos están desordenados

Permutación con una de sus inversiones resaltada. Una inversión puede denotarse por el par de lugares (2, 4) o por el par de elementos (5, 2). Las inversiones de esta permutación usando notación basada en elementos son: (3, 1), (3, 2), (5, 1), (5, 2) y (5,4).

En informática y matemáticas discretas , una inversión en una secuencia es un par de elementos que están fuera de su orden natural .

Definiciones

inversión

Sea una permutación . Hay una inversión de entre y si y . La inversión se indica mediante un par ordenado que contiene los lugares ^{[1] [2]} o los elementos . ^{[3] [4] [5]} ${\displaystyle \pi }$ ${\displaystyle \pi }$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i<j}$ ${\displaystyle \pi (i)>\pi (j)}$ ${\displaystyle (i,j)}$ ${\displaystyle {\bigl (}\pi (i),\pi (j){\bigr )}}$

El conjunto de inversiones es el conjunto de todas las inversiones. El conjunto de inversión de una permutación que utiliza notación basada en lugares es el mismo que el conjunto de inversión de la permutación inversa que utiliza notación basada en elementos con los dos componentes de cada par ordenado intercambiados. Del mismo modo, el conjunto de inversión de una permutación que utiliza notación basada en elementos es el mismo que el conjunto de inversión de la permutación inversa que utiliza notación basada en lugares con los dos componentes de cada par ordenado intercambiados. ^[6]

Las inversiones generalmente se definen para permutaciones, pero también se pueden definir para secuencias:
Sea una secuencia (o una permutación de conjuntos múltiples ^[7] ). Si y , el par de lugares ^{[7] [8]} o el par de elementos ^[9] se denomina 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 según la definición basada en elementos no son únicas, porque diferentes pares de lugares pueden tener el mismo par de valores.

Número de inversión

El número de inversión ^[10] de una secuencia , es la cardinalidad del conjunto de inversión. Es una medida común de clasificación (a veces llamada preclasificación) de una permutación ^[5] o secuencia. ^[9] El número de inversión está entre 0 e inclusive. Una permutación y su inversa tienen el mismo número de inversión. ${\displaystyle {\mathtt {inv}}(X)}$ ${\displaystyle X=\langle x_{1},\dots ,x_{n}\rangle }$ ${\displaystyle {\frac {n(n-1)}{2}}}$

Por ejemplo , ya que la secuencia está ordenada. Además, cuando es par (porque cada par es una inversión). Este último ejemplo muestra que un conjunto que intuitivamente está "casi ordenado" aún puede tener un número cuadrático de inversiones. ${\displaystyle {\mathtt {inv}}(\langle 1,2,\dots ,n\rangle )=0}$ ${\displaystyle n=2m}$ ${\displaystyle {\mathtt {inv}}(\langle m+1,m+2,\dots ,2m,1,2,\dots ,m\rangle )=m^{2}}$ ${\displaystyle (1\leq i\leq m<j\leq 2m)}$

El número de inversión es el número de cruces en el diagrama de flechas de la permutación, ^[6] la distancia tau de Kendall de la permutación desde la permutación de identidad y la suma de cada uno de los vectores relacionados con la inversión que se definen a continuación.

Otras medidas de clasificació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 "corridas" ordenadas dentro de la secuencia, la regla de Spearman (suma de distancias de cada elemento desde su lugar ordenado). posición), y el menor número de intercambios necesarios para ordenar la secuencia. ^{[11] 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 ) . ^[12]

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í se encuentra una lista de fuentes).

Este artículo utiliza el término vector de inversión ( ) como Wolfram . ^[13] Los dos vectores restantes a veces se denominan vector de inversión izquierda y derecha , pero para evitar confusión con el vector de inversión, este artículo los llama recuento de inversión izquierda ( ) y recuento de inversión derecha ( ). Interpretado como un número factorial, el recuento de inversión a la izquierda da las permutaciones colexicográficas inversas, ^[14] y el recuento de inversión a 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 (derecho) 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 mayor (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 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 ordenable muestra las 24 permutaciones de cuatro elementos (en la columna) con sus conjuntos de inversión basados ​​en lugares (en la columna pb), vectores relacionados con la inversión (en las columnas , y ) y números de inversión (en la columna # ). (Las columnas con letra más pequeña y sin encabezado son reflejos de las columnas que están al lado de ellas y se pueden usar para clasificarlas en orden colexicográfico ). ${\displaystyle \pi }$ ${\displaystyle v}$ ${\displaystyle l}$ ${\displaystyle r}$

Se puede ver que y siempre tienen los mismos dígitos, y que ambos están relacionados con el conjunto de inversión basado en lugares. 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 . Ordenar por Lex es lo mismo que ordenar por Lex . ${\displaystyle \pi }$ ${\displaystyle l}$ ${\displaystyle \pi }$ ${\displaystyle r}$

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

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

Si se asigna una permutación a cada conjunto de inversión utilizando la definición basada en lugares, el orden resultante de las permutaciones es el del permutoedro, donde una arista 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 una arista corresponde al intercambio de dos elementos en lugares consecutivos. Este gráfico de Cayley del grupo simétrico es similar a su permutoedro, pero con cada permutación reemplazada por su inversa.

Ver también

• Sistema de números factoriales
• Gráfico de permutación
• Transposiciones, transposiciones simples, inversiones y clasificación.
• Distancia Damerau-Levenshtein
• Paridad de una permutación

Secuencias en la OEIS :

• Secuencias relacionadas con la representación de bases factoriales.
• 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 ceros y unos 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 de Mahonia: A008302 (sus máximos de fila; números de Kendall-Mann: A000140)
• Número de gráficos etiquetados conectados con n aristas 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. Gratzer 2016, págs.221.
7. Bóna 2012, págs.57.
8. Cormen et al. 2001, págs.39.
9. Barth y Mutzel 2004, págs.183.
10. Mannila 1985.
11. Mahmoud 2000, págs.284.
12. Kleinberg y Tardos 2005, págs.225.
13. Weisstein, Eric W. "Vector de inversión" de MathWorld : un recurso web de Wolfram
14. Orden colex inverso de permutaciones finitarias (secuencia A055089 en la OEIS )

Bibliografía fuente

• Aigner, Martín (2007). "Representación de palabras". Un curso de enumeración . Berlín, Nueva York: Springer. ISBN 978-3642072536.
• Barth, Guillermo; Mutzel, Petra (2004). "Conteo cruzado bicapa simple y eficiente". Revista de aplicaciones y algoritmos de gráficos . 8 (2): 179-194. doi : 10.7155/jgaa.00088 .
• Bóna, Miklós (2012). "2.2 Inversiones en permutaciones de multiconjuntos". Combinatoria de permutaciones . Boca Ratón, FL: CRC Press. ISBN 978-1439850510.
• Comtet, Luis (1974). "6.4 Inversiones de una permutación de [n]". Combinatoria avanzada; el arte de las expansiones finitas e infinitas. Dordrecht, Boston: Pub D. Reidel. ISBN del condado 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 red. 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 . Pub Addison-Wesley. ISBN del condado 0201896850.
• Mahmoud, Hosam Mahmoud (2000). "Clasificación de datos no aleatorios". Clasificación: una teoría de la distribución . Serie Wiley-Interscience sobre matemáticas discretas y optimización. vol. 54. Wiley-IEEE. ISBN 978-0-471-32710-3.
• Pemmaraju, Sriram V.; Skiena, Steven S. (2003). "Permutaciones y combinaciones". Matemáticas discretas computacionales: 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, enero (ed.). Algoritmos y Complejidad . vol. 1 (2ª ed.). Elsevier. ISBN 978-0-444-88071-0.

Otras lecturas

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

Medidas de preclasificación

• Mannila, Heikki (abril de 1985). "Medidas de preclasificación y algoritmos de clasificación óptimos". Transacciones IEEE en computadoras . C-34 (4): 318–325. doi :10.1109/tc.1985.5009382.
• Estivill-Castro, Vladimir; Madera, Derick (1989). "Una nueva medida de preclasificación". Información y Computación . 83 (1): 111-119. doi : 10.1016/0890-5401(89)90050-3 .
• Skiena, Steven S. (1988). "Listas invasoras como medida de preclasificación". POCO . 28 (4): 755–784. doi :10.1007/bf01954897. S2CID  33967672.