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
Dejar ser una permutación . Si y , ya sea el par de lugares [1] [2] o el par de elementos[3] [4] [5] se denomina inversión de.
La inversión generalmente se define para permutaciones, pero también puede definirse para secuencias:
Seaser una secuencia (o permutación multiset [6] ). Si y , ya sea el par de lugares [6] [7] o el par de elementos[8] se llama inversión de.
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 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 [10] de una secuencia, es la cardinalidad del conjunto de inversión. Es una medida común de (pre) ordenación de una permutación [5] o secuencia. [8] Este valor está comprendido entre 0 y incluido.
Por ejemplo ya que la secuencia está ordenada. También como cada pareja es una inversión. Este último ejemplo muestra que un tipo que se ordena intuitivamente todavía puede tener un número cuadrático de inversiones.
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. [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]
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 . [13] 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 cuenta de inversión derecha (). Interpretado como un número factorial, el recuento de inversión de la izquierda da las permutaciones colexicográficas inversas, [14] y el recuento de inversión de la derecha da el índice lexicográfico.
Vector de inversión :
Con la definición basada en elementoses el número de inversiones cuyo componente más pequeño (a la derecha) es. [3]
- es el número de elementos en mas grande que antes de .
Cuenta de inversión izquierda :
Con la definición basada en el lugares el número de inversiones cuyo componente más grande (a la derecha) es.
- es el número de elementos en mas grande que antes de .
Cuenta de inversión derecha , a menudo llamado código de Lehmer :
con la definición basada en el lugares el número de inversiones cuyo componente más pequeño (izquierda) es.
- es el número de elementos en menor que después .
Ambas cosas y se puede 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 fila del diagrama de Rothe, mientras 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 inverso, y viceversa.
Ejemplo: todas las permutaciones de cuatro 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 ver que y siempre tienen los mismos dígitos, y eso y ambos están relacionados con el conjunto de inversión basada en el lugar. Los elementos no triviales de son las sumas de las diagonales descendentes del triángulo mostrado, y las 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).
El orden predeterminado de la tabla es el orden colex inverso por , que es lo mismo que orden colex por . Lex orden por es lo mismo que el orden lex por .
Permutaciones de 3 elementos para comparación | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
Orden débil de permutaciones
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 las 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
- 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
- ^ Aigner 2007 , págs.27.
- ^ Comtet 1974 , págs.237.
- ↑ a b Knuth 1973 , págs.11.
- ^ Pemmaraju y Skiena 2003 , págs.69 .
- ↑ a b Vitter y Flajolet 1990 , págs.459 .
- ↑ a b Bóna , 2012 , págs.57 .
- ^ Cormen y col. 2001 , págs.39.
- ↑ a b Barth y Mutzel , 2004 , págs.183 .
- ↑ a b Gratzer , 2016 , págs. 221.
- ^ Mannila, 1984 y pp318 .
- ^ Mahmoud 2000 , págs.284.
- ^ Kleinberg y Tardos 2005 , págs.225.
- ^ Weisstein, Eric W. "Inversión vector" De MathWorld Recursos Web --A Wolfram
- ^ Orden colex inverso de permutaciones finitarias (secuencia A055089 en la OEIS )
Bibliografía fuente
- 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.
Otras lecturas
- 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 Ciencias de la Computación . 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 .