Superpermutación

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 la concatenación de todas las permutaciones , también pueden ser más cortas (excepto en el caso trivial de n = 1) debido a que 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 ) . ^{[ 1 ]} 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 longitud 153. Una de estas 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 ): ^{[ 2 ]}

12345123 4152341253412354 1231452314253142 35142315 42312453 1243512431524312 5431 2 134 52134251 34215342 13542132 4513241532413524 1325413214532143 52143251 432154321

Para los casos de n > 5, aún no se ha demostrado la existencia de la superpermutación más pequeña ni un patrón para encontrarlas, pero sí se han hallado límites inferiores y superiores para las mismas.

Uno de los algoritmos más comunes para crear una superpermutación de orden${\displaystyle n}$es un algoritmo recursivo. Primero, la superpermutación de orden${\displaystyle n-1}$se divide en sus permutaciones individuales en el orden en que aparecieron en la superpermutación. Cada una de esas permutaciones se coloca junto a una copia de sí misma con un enésimo símbolo añadido 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. ^{[ 3 ]}

Por ejemplo, se puede crear una superpermutación de orden 3 a partir de una con 2 símbolos; partiendo de 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 de hecho es 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 larga que la más corta posible a medida que n aumenta más allá de ese valor. ^{[ 3 ]}

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 del inicio) para obtener la otra permutación. ^{[ 3 ]} Por ejemplo, la arista de 123 a 312 tiene un peso de 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 . La primera instancia de una superpermutación menor que la longitud${\displaystyle 1!+2!+\ldots +n!}$Fue hallado mediante una búsqueda informática sobre este método realizada por Robin Houston.

• 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 secuencias cíclicas.

• Ashlock, Daniel A.; Tillotson, Jenett (1993), "Construcción de superpermutaciones pequeñas y supercuerdas inyectivas mínimas", Congressus Numerantium , 93 : 91–98 , Zbl 0801.05004 
• Usuario anónimo de 4chan; Houston, Robin; Pantone, Jay; Vatter, Vince (25 de octubre de 2018). "Un límite inferior para la longitud del superpatrón más corto" (PDF) . Enciclopedia en línea de secuencias de enteros .

• El problema de la superpermutación mínima - Blog de Nathaniel Johnston
• Grime, James (29 de enero de 2018). "Superpermutaciones - Numberphile" (vídeo) . YouTube . Brady Haran . Consultado el 1 de febrero de 2018 .
• La publicación original de 4chan en /sci/ , archivada en warosu.org
• Tuit de Robin Houston que llamó la atención sobre la publicación de 4chan.
• Artículo sobre el problema de encontrar superpermutaciones cortas en la revista Quanta Magazine.