Superpermutaciones

El 16 de septiembre de 2011, un aficionado al anime subió al foro de Internet 4chan una pregunta de matemáticas relativa a la serie de televisión de culto 'La melancolía de Haruhi Suzumiya'. La primera temporada de la serie, en la que hay viajes por el tiempo, no se emitió originalmente en orden cronológico; una emisión posterior y una versión en DVD reordenaron los episodios.

Los seguidores de la serie debatieron en Internet acerca de cuál era el mejor orden de los episodios; el mensaje colgado en 4chan se preguntaba lo siguiente: si los espectadores quisiesen ver la serie ordenada de todas las maneras posibles, ¿cuál sería la lista con menos episodios que tendrían que ver?

En menos de una hora, alguien, de forma anónima, ofreció una respuesta. No se trataba de una solución completa, sino de una cota inferior del número de episodios requerido. El argumento, válido para series con cualquier número de episodios, mostraba que para los 14 de la primera temporada de Haruhi los espectadores tendrían que ver al menos 93.844.313.611 episodios para que no se les escapase ninguna ordenación. 

¡Es el origen de las superpermutaciones!

Una superpermutación es una cadena formada a partir de n símbolos de manera que las n! permutaciones de esos símbolos aparecen al menos una vez formando un bloque continuo de n caracteres en la cadena. Por ejemplo, con dos caracteres se tiene la superpermutación:

$$ABA$$

donde están las permutaciones AB y BA. 

Dada una superpermutación de orden n-1, para obtener una superpermutación de orden n sigue los pasos del siguiente algoritmo:

• Escribe las permutaciones de la última superpermutación en el orden en que aparecen.
• Duplica cada una de ellas y coloca entre ellas el nuevo elemento.
• Comprime el resultado utilizando todos los solapamientos posibles.

$$A$$

$$ABA$$

$$AB \vert BA$$

$$ABCAB \vert BACBA$$

$$ABCABACBA$$

$$ABC \vert BCA \vert CAB \vert BAC \vert ACB \vert CBA$$

$$ABCDABC \vert BCADBCA \vert CABDCAB\vert$$

$$\vert BAC DBAC\vert ACBDACB\vert CBADCBA$$

$$ABCDABCADBCABDCABACDBACBDACBADCBA$$

Vemos que las longitudes de las superpermutaciones son: L(1)=1, L(2)=3, L(3)=9 y L(4)=33. Siguiendo el proceso se obtendría L(5)=153. Cumplen la ecuación recursiva:

$$L(n)=L(n-1)+n! \rightarrow L(n)=1!+2!+3!+ \dots +n!$$

Para n=1,2,3,4 se obtienen las superpermutaciones más cortas y que son únicas.

¿Existe superpermutaciones de menor longitud que las que se obtienen de la fórmula anterior para cualquier valor de n?;

En 2013, Nathaniel Johnston demostró que para n>=5 las soluciones obtenidas por el algoritmo podían no ser únicas. En 2014, Ben Chafin demostró que para n=5 aunque no había superpermutaciones más cortas había 8 diferentes. Poco después Robin Houston encontro una superpermutación para n=6 con 872 caracteres, una menos que L(6)=873. En 2013 Aaron Williams propuso la fórmula:

$$L_2(n)=n!+(n-1)!+(n-2)! +(n-3)! +n-3$$

Sólo funciona para n>3 y para n<6 genera cadenas más largas que el algoritmo estándar: L2(4)=34, L2(5)=154. Ya L(6)=L2(6) pero a partir de ahí el método es cada vez más eficiente.

L2(7)=5908, 5 menos que L(7)=5915; L2(8)=46205, 28 menos que L(8)=46233; L2(9)=408966, 28 menos que L(9)=409113. En general:

$$L_2(n)-L(n)=n-3-L(n-4)$$

Sea un grafo dirigido donde los vértices son las diferentes permutaciones y las aristas tienen un peso que corresponde al número de elementos que hay que eliminar de una  permutación para obtener la siguiente. Por ejemplo, el paso de ABC a BCA supone quitar la A para ponerla al final. En cambio el paso de CAB a BAC supone quitar CA para ponerlo al final.

En el problema de las superpermutaciones queremos dar con la secuencia más corta posible de dígitos que sea una lista de todas las permutaciones, así que el objetivo consiste en 'viajar' a través de todas las permutaciones con el menor coste posible. Establecemos que el coste de cada arista es  el número de dígitos que tenemos que añadir al final de una permutación para obtener la siguiente. Houston lo convierte en el Problema del Viajante y mediante este algoritmo consigue superpermutaciones de n caracteres de longitud menor que L(n).