Forzando un bloqueo de teclado

Question

Una cerradura en particular en mi universidad tiene un teclado con los dígitos del 1 al 5. Cuando se presionan en la permutación correcta de esos cinco dígitos, la cerradura se abrirá.

Obviamente, dado que solo hay 120 permutaciones, podemos forzar la cerradura en 600 pulsaciones. ¡Pero podemos hacerlo mejor! La secuencia 1234512 en realidad prueba tres secuencias distintas con solo siete pulsaciones - 12345, 23451 y 34512.

¿Cuál es la estrategia más rápida para forzar esta cerradura?

(y para puntos adicionales, otras cerraduras con más números, contraseñas más largas, etc.)

(He intentado resolver este problema sin progresos significativos, en particular, las secuencias de De Bruijn no son directamente relevantes aquí)

Answer 1

Queremos encontrar una palabra sobre el alfabeto $\{1,\ldots,n\}$ que sea lo más corta posible y contenga todas las $n!$ permutaciones del alfabeto como infijos. Sea $\ell_n$ la longitud más corta alcanzable. Claramente, $$\tag1\ell_n\ge n!+(n-1).$$ Por supuesto, $(1)$ es algo optimista porque requiere superposiciones de $(n-1)$ entre todas las permutaciones consecutivas, pero eso solo es posible para permutaciones cíclicamente equivalentes. Dado que hay $(n-1)!$ clases de equivalencia bajo la equivalencia cíclica, y cambiar entre estas nos requiere "desperdiciar" un símbolo, encontramos que $$\tag2\ell_n\ge n!+(n-1)+(n-1)!-1=n!+(n-1)!+(n-2).$$ En particular, la desigualdad $(2)$ es ajustada para los primeros casos $\ell_1=1$, $\ell_2=3$ (de "121"), $\ell_3=9" (de "312313213"). Sin embargo, parece que $\ell_4=33$ (de "314231432143124313421341234132413").

Alimentando estos pocos valores en el motor de búsqueda de OEIS revela http://oeis.org/A180632 y vemos que los valores exactos parecen estar solo conocidos hasta $\ell_5=153$ (¡que es tu problema original)! Citando los límites conocidos desde allí, tenemos $$ \ell_n\ge n! + (n-1)! + (n-2)! + n-3$$ (lo cual supuestamente se puede mostrar de manera similar a como encontramos ($2)$ arriba) y $$\ell_n\le \sum_{k=1}^nk!.$$ Estos límites nos dicen que $152\le l_5\le 153$, pero se demostró en 2014 que de hecho $\ell_5=153$. El siguiente caso parece estar aún abierto: Las desigualdades solo nos dicen $867\le \ell_6\le 873$, pero otro resultado de 2014 muestra que $\ell_6\le 872$.

Answer 2

La respuesta de Hagen von Eitzen informa sobre el estado del arte. Dado que en el enlace proporcionado no hay un ejemplo de las ocho soluciones distintas de longitud de caracteres $\ell_5$, aquí tienes una. Lo calculé con un programa simple en python. También se encuentra en el artículo del 22 de agosto de 2014 [arXiv] donde Robin Houston presenta su candidato para una superpermutación mínima de 6 símbolos.

1234512341 5234125341 2354123145 2314253142 3514231542 
3124531243 5124315243 1254312134 5213425134 2153421354
2132451324 1532413524 1325413214 5321435214 3251432154
321

Editado: A instancias del OP, decidí publicar mi código en python 2. Es un script rápido y sucio y no es un ejemplo de código bien escrito. Se puede mejorar y optimizar de mil maneras, pero funciona. No lo publicaría en un sitio de programación, pero aquí estamos usando el sombrero de un matemático...

La idea básica es hacer crecer nuestra superpermutación paso a paso. Comenzamos desde 12345 y en cada paso identificamos la cola más larga que podría proporcionar una permutación aún no usada. Por ejemplo, en el segundo paso identificamos 2345, sobre el cual encontramos 23451 como la siguiente permutación, y agregamos 1 a nuestro resultado, por lo que ahora tenemos 123451. Continuando de esta manera encontramos una primera órbita completa de permutaciones cíclicas en 123451234. Después de eso, debemos agregar dos caracteres, ya que la siguiente permutación solo puede ser 23415, y nuestro resultado en crecimiento se convierte en 12345123415. Habrá puntos en los que tengamos tan pocos caracteres superpuestos posibles que podemos elegir entre diferentes nuevas permutaciones (por eso hay ocho soluciones óptimas distintas). En este caso, ordeno los posibles candidatos lexicográficamente y elijo el primero. Cuando no haya más permutaciones disponibles, el programa termina. Esto produce resultados óptimos si el alfabeto tiene hasta cinco caracteres. Con seis caracteres, mi programa produce una superpermutación de 873 caracteres, que se conjeturó óptima antes del artículo de Houston. Mi programa funciona con alfabetos de longitud arbitraria (si se le da suficiente tiempo para ejecutarse ;-) ) pero, como Houston demostró, su resultado no será óptimo. Houston llegó a su superpermutación más corta utilizando un solucionador heurístico de problemas de investigación de operaciones.

#!/usr/bin/python
# -*- coding: utf-8 -*-

## Cambia esto si quieres una salida paso a paso
verbose = False

## El alfabeto. También, la primera permutación con la que se trata,
## que define el orden lexicográfico para las elecciones posteriores.
A = '12345'

N = len(A)

## La cadena de resultado se inicializa con el propio alfabeto.
R = A

## Un diccionario para hacer un seguimiento de las permutaciones encontradas.
Done = { A: True }

# El paso básico de iteración.
def process():
    global R, Done
    # t representa cuántos caracteres necesitamos agregar.
    # Primero probamos con uno, luego aumentamos...
    for t in range(1,N):
        # h es el muñón inicial (la "cabeza") de nuestra nueva permutación.
        h=R[t-N:]
        while len(h) < N:
            # Una forma grosera de encontrar los caracteres que aún faltan
            # en la nueva permutación que estamos construyendo.
            for c in [ x for x in A if x not in h ]:
                h += c
                break
        if h not in Done:
            # Se encontró una nueva permutación, actualiza las globales y devuélvela.
            Done[h] = True
            R += h[-t:]
            return h
    # ¡Todas las permutaciones posibles encontradas!
    return ''

p = A
while p != '':
    if verbose:
        print 'encontrado', p
    p = process()

print R
print len(R), 'bytes para', len(Done.keys()), 'permutaciones de', N, 'objetos'