Una superpermutación mÃnima es la cadena de sÃmbolos de longitud en mÃnima en la que aparecen todas las permutaciones de esos sÃmbolos en algún punto de la cadena.
Por ejemplo con los números 1, 2 y 3 serÃa 123121321 porque cualquier cadena (ej. 312) aparece en su interior; y asà con todas las combinaciones de 1-2-3.
Examinando el problema para n dÃgitos, de forma genérica, para n=1 la cadena es 1 y para n=2 la cadena serÃa 121, que contiene tanto 12 como 21. Para n=3 es 123121321 – el asunto crece rápido.
Ahora bien, para n=4 la cadena es
123412314231243121342132413214321
una complicación descomunal respecto a la solución anterior.
Y para n=5 se desconoce todavÃa la solución. En otras palabras: se conocen ciertas soluciones con todos los sÃmbolos 1-2-3-4-5 (al fin y al cabo hay 120 combinaciones y se podrÃan hasta poner todas seguidas) pero no cuál es la solución mÃnima, la superpermutación. Es tremendamente difÃcil de calcular por fuerza bruta, incluso con potentes ordenadores.
Asà que a lo mejor podrÃas encontrarla tú.
(VÃa MathPuzzle.)
# Enlace Permanente
via Microsiervos http://ift.tt/1fAomJj