Bruteforcing un bloqueo del teclado

Question

Un particular de bloqueo en mi universidad tiene un teclado con los dígitos 1-5. Cuando se pulsa en la correcta permutación de los cinco dígitos, se abrirá la cerradura.

Obviamente, dado que sólo hay 120 permutaciones, podemos bruteforce el bloqueo en 600 prensas. Pero podemos hacerlo mejor! La secuencia 1234512 hecho pruebas de tres secuencias distintas, con sólo siete prensas - 12345, 23451y 34512.

¿Cuál es el más rápido de la estrategia a la fuerza bruta de este bloqueo?

(y para los puntos de bonificación, las demás cerraduras con más números, más contraseñas, etc.)

(Me he tomado un par de puñaladas en este problema con el progreso no hablar de - en particular, De Bruijn secuencias no son directamente relevantes aquí)

Answer 1

Queremos encontrar una palabra sobre el alfabeto $\{1,\ldots,n\}$ que es tan corto como sea posible y contiene todos los $n!$ permutaciones de las letras del alfabeto infijos. Deje $\ell_n$ denotar el menor alcanzable longitud. Claramente, $$\tag1\ell_n\ge n!+(n-1).$$ Por supuesto, $(1)$ es optimista porque requiere $(n-1)$-solapamientos entre todos consecutivos permutaciones, sino que sólo es posible para cyclicly equivalente permutaciones. Como hay $(n-1)!$ clases de equivalencia bajo cíclico de equivalencia, y el cambio entre estos nos obliga a "residuos", un símbolo, nos encontramos con que $$\tag2\ell_n\ge n!+(n-1)+(n-1)!-1=n!+(n-1)!+(n-2).$$ En particular, la desigualdad $(2)$ es aguda para el primer par de casos $\ell_1=1$, $\ell_2=3$ (de "121"), $\ell_3=9$ (de "312313213"). Sin embargo, parece que ese $\ell_4=33$ (de "314231432143124313421341234132413").

La alimentación de estos pocos valores en la OEIS motor de búsqueda revela http://oeis.org/A180632 y vemos que los valores exactos que parece ser conocido sólo a $\ell_5=153$ (lo cual es su problema original)! Citando el conocido límites a partir de ahí, hemos $$ \ell_n\ge n! + (n-1)! + (n-2)! + n-3$$ (que, supuestamente, puede ser demostrado de manera similar a cómo lo encontramos ($2)$ anterior) y $$\ell_n\le \sum_{k=1}^nk!.$$ Estos límites nos dicen que $152\le l_5\le 153$, pero se ha demostrado en el 2014 que en el hecho de $\ell_5=153$. El siguiente caso parece ser todavía abierto: Las desigualdades sólo nos dirá $867\le \ell_6\le 873$, pero otro de los resultados de 2014 muestra que el $\ell_6\le 872$.

Answer 2

Hagen von Eitzen la respuesta de los informes del estado de la técnica. Ya que en el enlace no hay ningún ejemplo de los ocho distintos $\ell_5$-carácter de largo soluciones, aquí va uno. He calculado que con un simple programa en python. También se encuentra en el papel de Agosto. 22, 2014 [arXiv] donde Robin Houston, expone su candidato para un mínimo de superpermutation de 6 símbolos.

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

Editado: le Pregunte por el OP, me decidí a publicar mi python 2 código. Es una rápida y sucia de secuencia de comandos y no hay ningún ejemplo de código escrito. Puede ser mejorado y optimizado en un sin número de maneras, pero funciona. Yo no lo publiques en una programación de sitio, pero aquí andamos de un matemático del sombrero...

La idea básica es hacer crecer nuestro superpermutation paso por paso. Partimos de 12345 y en cada paso que identificar la cola más larga que podría proporcionar una permutación aún sin explotar. Por ejemplo, en el segundo paso se identifican 2345, en la que nos encontramos 23451 como la siguiente permutación, y añadimos 1 de nuestro resultado, así que ahora tenemos 123451. Continuar de esta manera nos encontramos con un primer conjunto de la órbita de permutaciones cíclicas en 123451234. Después de eso, tenemos que añadir dos personajes, ya que la siguiente permutación sólo puede ser 23415, y al crecimiento de nuestro resultado se convierte en 12345123415. Vamos a tener momentos donde tenemos tan pocos posible la superposición de personajes que podemos elegir entre diferentes permutaciones (por eso hay ocho distintas soluciones óptimas). En este caso, el fin de los posibles candidatos lexicográficamente y elegir el primero. Cuando no hay más disponibles permutaciones, se sale del programa. Este rendimientos óptimos resultados si el alfabeto es de hasta cinco caracteres. Con seis personajes, mi programa se obtiene un superpermutation de 873 personajes, que conjeturó óptimo antes de Houston papel. Mi programa funciona con alfabetos de longitud arbitraria (si se les da suficiente tiempo para ejecutar ; -) ), pero, como Houston demostró, su resultado no será óptimo. Houston llegó a su menor superpermutation el uso de una heurística solucionador de problemas de investigación de operaciones.

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

## Change this if you want a step-by-step output
verbose = False

## The alphabet. Also, the first permutation dealt with,
## which defines lexicographic ordering for subsequent choices.
A = '12345'

N = len(A)

## The result string is initialized with the alphabet itself.
R = A

## A dictionary to keep track of the found permutations.
Done = { A: True }

# The basic iteration step.
def process():
    global R, Done
    # t represents how many characters we need to add.
    # First we try with one, then we increase...
    for t in range(1,N):
        # h is the initial stub (the "head") of our new permutation.
        h=R[t-N:]
        while len(h) < N:
            # A crude way to find the characters still missing from 
            # the new permutation we are building.
            for c in [ x for x in A if x not in h ]:
                h += c
                break
        if h not in Done:
            # Found new permutation, update globals and return it.
            Done[h] = True
            R += h[-t:]
            return h
    # All possible permutations found!
    return ''

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

print R
print len(R), 'bytes for', len(Done.keys()), 'permutations of', N, 'objects'