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 compuestas 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 es se muestra a continuación, mientras que se puede obtener otro de la misma longitud cambiando todos los cuatros y cincos en la segunda mitad de la cuerda (después del 2 en negrita ): [1]
1234512341523412534123541231452314253142351423154231245312435124315243125431 2 13452134251342153421354213245132415324135241 32541321453214352143251432154321
Para los casos de n > 5, aún no se ha demostrado una superpermutación más pequeña ni un patrón para encontrarlos, pero se han encontrado sus límites superior e inferior.
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í mismas con un enésimo símbolo agregado entre las dos copias. Finalmente, cada estructura resultante se coloca una al lado de 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 largo que el más corto posible a medida que n aumenta más allá de eso. [2]
Otra forma de encontrar superpermutaciones consiste en crear un gráfico donde cada permutación sea un vértice y cada permutación esté conectada por una arista. Cada borde tiene un peso asociado; el peso se calcula viendo cuántos caracteres se pueden agregar al final de una permutación (eliminando el mismo número de caracteres desde el principio) para dar como resultado 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 gráfico creado es una superpermutación, y el problema de encontrar el camino con el peso más pequeño se convierte en una forma de El problema del viajante . Robin Houston encontró el primer caso de una superpermutación menor que la longitud mediante una búsqueda por computadora sobre este método.
En septiembre de 2011, un cartel anónimo en el foro 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 . + ( norte −1)! + ( norte −2)! + n − 3. [3] En referencia a la serie de anime japonesa The Melancholy of Haruhi Suzumiya , el problema se presentó en el tablero de imágenes como "El problema de Haruhi": [4] si querías ver los 14 episodios de la primera temporada de la serie en cada orden posible, ¿cuál sería la cadena más corta de episodios que necesitarías ver? [5] La prueba de este límite inferior se hizo de interés público general en octubre de 2018, después de que el matemático e 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 enteras (OEIS). [5] [6] Una versión publicada de esta prueba, acreditada al "póster anónimo de 4chan", aparece en Engen y Vatter (2021). [7] Para "El problema de Haruhi" específicamente (el caso de 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 alrededor de 4,3 millones de años. [8]
El 20 de octubre de 2018, adaptando 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 y matemático de ciencia ficción Greg Egan ideó un algoritmo para producir superpermutaciones de longitud n . + ( norte −1)! + ( norte −2)! + ( norte −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 fue 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 también existen superpermutaciones más cortas similares para valores de n > 7 sigue siendo una cuestión abierta. El mejor límite inferior actual (ver sección anterior) para n = 7 sigue siendo 5884.
{{cite journal}}: Mantenimiento CS1: nombres numéricos: lista de autores ( enlace ){{cite web}}: Mantenimiento CS1: nombres numéricos: lista de autores ( enlace )