En matemáticas combinatorias , una superpermutación de n símbolos es una cadena que contiene cada permutación de n símbolos como una subcadena . Si bien las superpermutaciones triviales pueden estar formadas simplemente por cada permutación concatenada, las superpermutaciones también pueden ser más cortas (excepto en el caso trivial de n = 1) porque se permite la superposición. Por ejemplo, en el caso de n = 2, la superpermutación 1221 contiene todas las permutaciones posibles (12 y 21), pero la cadena más corta 121 también contiene ambas permutaciones.
Se ha demostrado que para 1 ≤ n ≤ 5, la superpermutación más pequeña en n símbolos tiene longitud 1! + 2! + … + n ! (secuencia A180632 en la OEIS ). Las primeras cuatro superpermutaciones más pequeñas tienen longitudes respectivas 1, 3, 9 y 33, formando las cadenas 1, 121, 123121321 y 123412314231243121342132413214321. Sin embargo, para n = 5, hay varias superpermutaciones más pequeñas que tienen una longitud de 153. Una de esas superpermutaciones se muestra a continuación, mientras que otra de la misma longitud se puede obtener intercambiando todos los cuatros y cincos en la segunda mitad de la cadena (después del 2 en negrita ): [1]
1234512341523412534123541231452314253142351423154231245312435124315243125431 2 13452134251342153421354213245132415324 13524132541321453214352143251432154321
Para los casos de n > 5, aún no se ha demostrado una superpermutación mínima ni un patrón para encontrarlas, pero se han encontrado límites inferior y superior para ellas.
Uno de los algoritmos más comunes para crear una superpermutación de orden es un algoritmo recursivo. Primero, la superpermutación de orden se divide en sus permutaciones individuales en el orden en que aparecieron en la superpermutación. Luego, cada una de esas permutaciones se coloca junto a una copia de sí misma con un símbolo n -ésimo agregado entre las dos copias. Finalmente, cada estructura resultante se coloca junto a la otra y se fusionan todos los símbolos idénticos adyacentes. [2]
Por ejemplo, se puede crear una superpermutación de orden 3 a partir de una con 2 símbolos; comenzando con la superpermutación 121 y dividiéndola en las permutaciones 12 y 21, las permutaciones se copian y se colocan como 12312 y 21321. Se colocan juntas para crear 1231221321, y los 2 adyacentes idénticos en el medio se fusionan para crear 123121321, que es de hecho una superpermutación de orden 3. Este algoritmo da como resultado la superpermutación más corta posible para todos los n menores o iguales a 5, pero se vuelve cada vez más larga que la más corta posible a medida que n aumenta más allá de eso. [2]
Otra forma de encontrar superpermutaciones consiste en crear un grafo donde cada permutación es un vértice y cada permutación está conectada por una arista. Cada arista tiene un peso asociado; el peso se calcula viendo cuántos caracteres se pueden agregar al final de una permutación (eliminando la misma cantidad de caracteres desde el principio) para obtener la otra permutación. [2] Por ejemplo, la arista de 123 a 312 tiene peso 2 porque 123 + 12 = 12312 = 312. Cualquier camino hamiltoniano a través del grafo creado es una superpermutación, y el problema de encontrar el camino con el menor peso se convierte en una forma del problema del viajante . El primer ejemplo de una superpermutación menor que la longitud fue encontrado usando una búsqueda en computadora sobre este método por Robin Houston.
En septiembre de 2011, un cartel anónimo en el tablero de Ciencias y Matemáticas (" /sci/ ") de 4chan demostró que la superpermutación más pequeña en n símbolos ( n ≥ 2) tiene al menos una longitud n ! + ( n −1)! + ( n −2)! + n − 3. [3] En referencia a la serie de anime japonesa La melancolía de Haruhi Suzumiya , particularmente el hecho de que originalmente se transmitió como una narrativa no lineal , el problema se presentó en el tablero de imágenes como "El problema de Haruhi": [4] si quisieras ver los 14 episodios de la primera temporada de la serie en todos los órdenes posibles, ¿cuál sería la cadena más corta de episodios que necesitarías ver? [5] La prueba de este límite inferior llegó al interés del público en general en octubre de 2018, después de que el matemático y científico informático Robin Houston tuiteara al respecto. [3] El 25 de octubre de 2018, Robin Houston, Jay Pantone y Vince Vatter publicaron una versión refinada de esta prueba en la Enciclopedia en línea de secuencias de enteros (OEIS). [5] [6] Una versión publicada de esta prueba, atribuida a un "autor anónimo de 4chan", aparece en Engen y Vatter (2021). [7]
En el caso específico de "El problema de Haruhi" (el caso de los 14 símbolos), los límites inferior y superior actuales son 93.884.313.611 y 93.924.230.411, respectivamente. [3] Esto significa que ver la serie en todos los órdenes posibles requeriría unos 4,3 millones de años. [8]
El 20 de octubre de 2018, al adaptar una construcción de Aaron Williams para construir caminos hamiltonianos a través del gráfico de Cayley del grupo simétrico , [9] el autor de ciencia ficción y matemático Greg Egan ideó un algoritmo para producir superpermutaciones de longitud n ! + ( n −1)! + ( n −2)! + ( n −3)! + n − 3. [2] Hasta 2018, estas eran las superpermutaciones más pequeñas conocidas para n ≥ 7. Sin embargo, el 1 de febrero de 2019, Bogdan Coanda anunció que había encontrado una superpermutación para n = 7 de longitud 5907, o ( n ! + ( n −1)! + ( n −2)! + ( n −3)! + n − 3) − 1, que era un nuevo récord. [2] El 27 de febrero de 2019, utilizando ideas desarrolladas por Robin Houston, Egan produjo una superpermutación para n = 7 de longitud 5906. [2] Si existen también superpermutaciones más cortas similares para valores de n > 7 sigue siendo una pregunta abierta. El mejor límite inferior actual (ver la sección anterior) para n = 7 sigue siendo 5884.
