¿Cuál es la cadena más corta que contiene todas las permutaciones de un alfabeto?

Question

¿Cuál es la cadena más corta $S$ sobre un alfabeto de tamaño $n$ , tal que toda permutación del alfabeto es una subcadena de $S$ ?

Editar 2019-10-17: Esto se llama una superpermutación, y hay una página de wikipedia que hace un seguimiento de los mejores resultados. Resulta que el problema sigue abierto.

Answer 1

He aquí algunas reflexiones: dada una permutación $abcde$ , puedes generar todas sus rotaciones cíclicas sin coste adicional: $abcdeabcd$ . Entonces querrás poner en mayúsculas los símbolos de los números más grandes, así que repetimos el símbolo más profundo, en este caso $a$ completan la permutación con $e$ y generar todas las rotaciones cíclicas: $abcdeabcdaebcda$ . Hasta ahora hemos generado todas las rotaciones cíclicas de $abcde$ y $bcdae$ . Obsérvese que el primer $n-1$ los caracteres se giran. Seguimos generando todas las rotaciones cíclicas de $cdabe,dabce$ y luego tenemos que traer un símbolo menos: $\ldots dabcedabcadebcad$ . Así que pasamos de $dabce$ a $bcade$ . Esto corresponde a la rotación del centro $n-2$ caracteres, seguido de la habitual rotación de $n-1$ personajes. Ahora volvemos a la operación anterior (rotación de $n-1$ ), aplicando ocasionalmente la nueva rotación, hasta que nos atasquemos; entonces tendríamos que hacer una rotación del medio $n-3$ caracteres, etc.

Conjeturo que el esquema anterior es óptimo; el lector diligente puede calcular recursivamente su longitud.

Answer 2

Investigué esta cuestión hace 20 años y descubrí que la longitud de la cadena más corta que contiene todas las permutaciones de n objetos es la indicada en http://www.notatt.com/permutations.pdf . Creamos un algoritmo informático para generar todas las cadenas posibles que contienen todas las permutaciones de n objetos y demostramos esta longitud mínima mediante fuerza bruta para alfabetos de hasta 11 objetos. Nunca pudimos encontrar una prueba de que nuestro algoritmo generara las cadenas más cortas para cualquier n y me encantaría que alguien retomara este tema. Me he dado cuenta de que la mayoría de los matemáticos desestiman este tema como si ya estuviera hecho, cuando en realidad, al examinarlo de cerca, no se ha demostrado. Si alguien conoce una prueba de este tipo, le ruego que la comunique. Puede encontrar nuestro artículo en Minimal Superpermutations, Ashlock D., y J. Tillotson, Congressus Numerantium 93(1993), 91-98.

Answer 3

NB] Este argumento es incorrecto, y el error es señalado por Yuval en los comentarios más abajo. En efecto, se puede utilizar el gráfico de De Bruijn para obtener todas las permutaciones, exactamente como lo describo a continuación, pero, como implica el comentario de Yuval, también se obtendrán muchas no permutaciones. La longitud de la cadena $S$ no es lo que mi argumento dice que es, y el problema de la secuencia de LONGITUD MÍNIMA parece requerir un argumento diferente.

Esto es muy peligroso porque todos esos puntos inmerecidos pueden hacer que alguien descarte lo que podría ser una pregunta interesante y difícil.

Dado que hay $n!$ permutaciones de $n$ símbolos, la cadena $S$ debe tener una longitud al menos $n!+n-1$ . Es decir, debe haber $n!$ posiciones de inicio para una permutación, y la última posición de inicio debe ser sucedida por $n-1$ símbolos.

De hecho, existe una cadena de este tipo, que se obtiene a partir de un camino euleriano en el grafo de De Bruijn $B(n,n)$ . Se trata de un grafo dirigido cuyos vértices son todas las cadenas de $n-1$ símbolos distintos, con una arista dirigida desde $u$ a $v$ si hay un símbolo $s$ tal que $v$ tiene la forma $u_1s$ , donde $u_1$ es $u$ con el símbolo más a la izquierda borrado. Etiquetamos la arista con $s$ . Cada vértice tiene el mismo grado de entrada y de salida, por lo que el grafo tiene un camino euleriano. Las etiquetas de las aristas de cualquier camino de este tipo, junto con la cadena donde termina el camino, da una secuencia mínima del tipo que se desea. Véase este artículo de Wikipedia http://en.wikipedia.org/wiki/De_Bruijn_sequence para la terminología, las referencias y una buena explicación.