¿Cuál es la secuencia más corta que contiene cada permutación de$1..n$?

Question

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

¿Cómo se puede crear una lista de números, por lo que tomando $n$ consecutivos elementos de la lista, es posible obtener cada permutación de los números de 1 a $n$?

Voy a explicarme:

El más corto de la lista que contiene cada permutación de los números de 1 a 2 es: $$1, 2, 1$$ Que contiene (1, 2) y (2, 1).

Con los números de 1 a 3, se vería algo como esto: $$1, 2, 3, 1, 2, 1, 3, 2, 1$$ Contiene (1, 2, 3), (1, 3, 2), (2, 1, 3), ...

Nota: no estoy seguro de que este es el más corto de la lista de posibles.

Hay alguna forma de encontrar el más pequeño de la lista de números de 1 a $n$?

Answer 1

Usted está buscando secuencias de Bruijn. Ese término de la búsqueda debe encontrarle lo que usted desea.

Answer 2

Una referencia: http://people.inf.ethz.ch/zeugen/papers/zal_ipl11_perms.pdf