viernes, 11 de abril de 2014

1299 - Supermutaciones mínimas


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
Share/Bookmark

11 comentarios:

  1. El mismo Ed manda a la fuente de estos resultados: http://arxiv.org/pdf/1303.4150v1.pdf

    ResponderEliminar
  2. En dicho artículo los autores indican que para las 120 permutaciones de la cadena "12345" hay 2 soluciones de largo 153 dígitos.

    Por 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)

    ResponderEliminar
  3. 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.
    Me 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.

    ResponderEliminar
    Respuestas
    1. Otro problema similar puede ser:
      ¿Cuáles 2 permutaciones, de las 120, se pueden representar en una cadena de longitud mínima?
      ¿Cuáles 3 ......
      .......

      Vicente iq.

      Eliminar
    2. Vicente:
      Para 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

      Eliminar
  4. A lo mucho se pueden reunir 5 permutaciones distintas con una longitud mínima de 9: ABCDEABCD

    ResponderEliminar
    Respuestas
    1. Esta línea me parece interesante y es una de las que yo apuntaba.
      Con 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.

      Eliminar
  5. 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

    ResponderEliminar
    Respuestas
    1. Muy interesante esta variante !.

      Vicente iq.

      Eliminar
  6. http://www.njohnston.ca/2014/08/all-minimal-superpermutations-on-five-symbols-have-been-found/

    ResponderEliminar

Si quieres deja un comentario, si la entrada tiene mas de 15 dias deberás esperar a que la autorice y por favor si no tienes gmail deja tu nombre si no quedas como anónimo. Gracias!