En matemática combinatoria , una superpermutación en n símbolos es una cadena que contiene cada permutación de n símbolos como una subcadena . Mientras que las superpermutaciones triviales pueden estar formadas simplemente por cada permutación listada juntas, 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 posibles permutaciones (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 una longitud de 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 la longitud 153. Una de estas superpermutaciones es se muestra a continuación, mientras que se puede obtener otro de la misma longitud cambiando todos los cuatro y cinco en la segunda mitad de la cadena (después del 2 en negrita ): [1]
1234512341523412534123541231452314253142351423154231245312435124315243125431 2 1345213425134215342135421324513241532413524132541321453214352143251432154321
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 límites inferior y superior para ellos.
Encontrar superpermutaciones
Uno de los algoritmos más comunes para crear una superpermutación de orden. es un algoritmo recursivo. Primero, la superpermutación del ordense divide en sus permutaciones individuales en el orden en que aparecieron en la superpermutación. Cada uno de los permutación se colocan entonces junto a una copia de sí mismos con un n º símbolo añadido en entre las dos copias. Finalmente, cada estructura resultante se coloca una al lado de la otra y todos los símbolos idénticos adyacentes se fusionan. [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 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 todo n menor o igual 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 es un vértice y cada permutación está conectada por un borde. 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, el borde de 123 a 312 tiene un 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 . La primera instancia de una superpermutación menor que la longitudfue encontrado usando una búsqueda por computadora en este método por Robin Houston. [3]
Límites inferior y superior
Aún no se ha resuelto un algoritmo para encontrar la superpermutación más pequeña para 6 o más símbolos. Sin embargo, varias pruebas han reducido gradualmente los fuertes límites superior e inferior del problema a lo largo del tiempo.
Límites inferiores, o el problema de Haruhi
En septiembre de 2011, un póster 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. [4] En referencia a la serie de anime japonesa La melancolía de Haruhi Suzumiya , el problema se presentó en el tablero de imágenes como "El problema de Haruhi": si querías ver los 14 episodios de la primera temporada de la serie en cada orden posible, ¿cuál sería la serie más corta de episodios que necesitaría 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. [4] 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, acreditada al "Cartel anónimo de 4chan", aparece en Engen y Vatter ( 2019 ). [7] Para "El problema de Haruhi" específicamente (el caso de 14 símbolos), el límite inferior es actualmente al menos 93,884,313,611, y el límite superior es como máximo 93,924,230,411. [4]
Límites superiores
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 , [8] Greg Egan ideó un algoritmo para producir superpermutaciones de longitud n . + ( n −1)! + ( n −2)! + ( n −3)! + n - 3. [2] Hasta 2018, estas fueron 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 registro. [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 pregunta abierta. El mejor límite inferior actual (ver la sección anterior) para n = 7 sigue siendo 5884.
Ver también
- Superpatrón , una permutación que contiene cada permutación de n símbolos como un patrón de permutación
- Secuencia de De Bruijn , un problema similar con las secuencias cíclicas
Otras lecturas
- Ashlock, Daniel A .; Tillotson, Jenett (1993), "Construcción de pequeñas superpermutaciones y supercuerdas inyectables mínimas", Congressus Numerantium , 93 : 91–98, Zbl 0801.05004
- Póster anónimo de 4chan; Houston, Robin; Pantone, Jay; Vatter, Vince (25 de octubre de 2018). "Un límite inferior en la longitud del superpatrón más corto" (PDF) . Enciclopedia en línea de secuencias de enteros .
Referencias
- ^ Johnston, Nathaniel (28 de julio de 2013). "No unicidad de las superpermutaciones mínimas" . Matemáticas discretas . 313 (14): 1553-1557. arXiv : 1303.4150 . Código bibliográfico : 2013arXiv1303.4150J . doi : 10.1016 / j.disc.2013.03.024 . Zbl 1368.05004 . Consultado el 16 de marzo de 2014 .
- ^ a b c d e f Egan, Greg (20 de octubre de 2018). "Superpermutaciones" . gregegan.net . Consultado el 15 de enero de 2020 .
- ^ Houston, Robin (21 de agosto de 2014), "Abordando el problema de superpermutación mínima", arXiv : 1408.5108 [ math.CO ]
- ^ a b c Griggs, Mary Beth. "Una publicación anónima de 4chan podría ayudar a resolver un misterio matemático de hace 25 años" . The Verge .
- ^ a b Klarreich, Erica (5 de noviembre de 2018). "El escritor de ciencia ficción Greg Egan y el problema de la permutación avanzada del genio de las matemáticas anónimo" . Revista Quanta . Consultado el 21 de junio de 2020 .
- ^ Póster anónimo de 4chan; Houston, Robin; Pantone, Jay; Vatter, Vince (25 de octubre de 2018). "Un límite inferior en la longitud del superpatrón más corto" (PDF) . OEIS . Consultado el 27 de octubre de 2018 .
- ^ Engen, Michael; Vatter, Vincent (2021), "Containing all permutations", American Mathematical Monthly , 128 (1): 4–24, doi : 10.1080 / 00029890.2021.1835384
- ^ Aaron, Williams. "Hamiltonicidad del Cayley Digraph en el grupo simétrico generado por σ = (1 2 ... n) y τ = (1 2)". arXiv : 1307.2549v3 .
enlaces externos
- El problema de la superpermutación mínima - blog de Nathaniel Johnston
- Grime, James. "Superpermutaciones - Numberphile" (video) . YouTube . Brady Haran . Consultado el 1 de febrero de 2018 .
- La publicación de 4chan en / sci / , archivada en warosu.org
- Tweet de Robin Houston, que llamó la atención sobre la publicación de 4chan