Ed Pegg publicó en su página lo siguiente:
"123412314231243121342132413214321 tiene todas las permutaciones posibles de "1234", y es mínimo. (En otras palabras este es el menor número en el cual están incluidas las 24 permutaciones posibles que se pueden formar con "1234")
La menor cadena para "12345" es aún desconocida, a estas cadenas se las llama supermutaciones mínimas y son mucho mas difíciles de encontrar que las secuencias de DeBrujin."
Pregunta : ¿Cuál es la supermutación mínima para "123"?
Desafío : ¿Cuál es la supermutación mínima para "12345" que pueden encontrar?
Si lo quieres compartir o guardar
Entradas
El mismo Ed manda a la fuente de estos resultados: http://arxiv.org/pdf/1303.4150v1.pdf
ResponderEliminarEn dicho artículo los autores indican que para las 120 permutaciones de la cadena "12345" hay 2 soluciones de largo 153 dígitos.
ResponderEliminarPor mi parte, con un código elemental de fuerza bruta, lo único que he podido lograr es generar en unos pocos segundos soluciones del mismo largo (153 dígitos), por ejemplo las dos siguientes:
25431254321543251432541325423154235142354123542135425314253412534215342
51342524135241532415234152431524513245123451243512453124521345214352145321452314
52 (153)
42531425341253421534251342543125432154325143254132542315423514235412354
21354245132451234512435124531245213452143521453214523145241352415324152341524315
24 (153)
Supongo que los autores le habrán dedicado tiempo y esfuerzo a buscar la solución óptima. Por mi parte creo que sería interesante buscar soluciones óptimas por aproximación parcial.
ResponderEliminarMe explico: de las 120 permutaciones, intentar encontrar el código de longitud mínima para las 2 primeras permutaciones; a continuación para las 3 primeras, y así sucesivamente.
Se puede introducir un ratio de eficacia de la solución como:
(nº de permutaciones incluidas) / 120 ;(para el caso de las 120 permutaciones; o dividir por 2 para el caso de las 2 primeras permutaciones).
vicente Iq.
Otro problema similar puede ser:
Eliminar¿Cuáles 2 permutaciones, de las 120, se pueden representar en una cadena de longitud mínima?
¿Cuáles 3 ......
.......
Vicente iq.
Vicente:
EliminarPara dos permutaciones es fácil ver que repitiendo el primero y el sexto dígito obtenemos una supermutacion minima de 6 dígitos.
Es decir ABCDEA incluye ABCDE Y BCDEA
En el caso de los inversos se necesitaran 9 dígitos ABCDEDCBA
A lo mucho se pueden reunir 5 permutaciones distintas con una longitud mínima de 9: ABCDEABCD
ResponderEliminarEsta línea me parece interesante y es una de las que yo apuntaba.
EliminarCon longitud 6 podemos contemplar 2 permutaciones como máximo.
Con longitud 7 podemos contemplar 3.
....
Pero este crecimiento no es lineal, no se cumple siempre que con longitud n podamos tener n-4 permutaciones. Si fuera así con 124 dígitos tendríamos las 120. Aunque podría ser ya que el autor no dice que 153 sea el mínimo, o eso he entendido.
La variante que propone Claudio de leer también las permutaciones no solo de derecha a izquierda si no de izquierda a derecha también parece que promete.
Vicente iq.
Creo que otra variante sería tomar en cuenta las permutaciones de derecha a izquiera, así por ejemplo en ABCDEABCD tendríamos 10 permutaciones distintas, y se podrían achicar la cantidad de dígitos
ResponderEliminarMuy interesante esta variante !.
EliminarVicente iq.
http://www.njohnston.ca/2014/08/all-minimal-superpermutations-on-five-symbols-have-been-found/
ResponderEliminarA por el de 6 !!!,
EliminarVicente iq.