Minimal Superpermutations

propuesto por josejuan

Obtener una cadena de longitud mínima que contenga todas las permutaciones de n símbolos.

Enunciado
Fuente original

Dado un número n, generar la cadena de menor longitud JUSTIFICANDO LA RESPUESTA, tal que todas las permutaciones de n símbolos se encuentren en dicha cadena.

Por ejemplo, si n=2, una cadena posible sería

"12121"

Porque contiene las permutaciones de "12" que son 12", "21.

Sin embargo, se pide la de menor longitud y esa es la cadena

"121" ó "212"

y cualquier de estas dos serían correctas.

Para 1 <= n <= 4 tendríamos:

1 1
2 121
3 123121321
4 123412314231243121342132413214321

(aunque hay otras cadenas con igual longitud que también valdrían, se pide obtener una
cualquiera de ellas).

Ver todo el enunciado

Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

5 Soluciones

Dar mi solución

0votos
Minimal Superpermutations en Haskell
por

josejuan

hace 6 años

El algoritmo trivial (concatenar permutaciones hasta terminar) puede hacerse en tiempo casi lineal O(p), lo que pasa que como el número de permutaciones es p=n! resulta que el coste práctico respecto el nº de símbolos es O(n!), aún así puede mejorarse mucho este algoritmo. La pena es que no sirve (ver A007489).

Dar mi solución