algoritmo de búsqueda

Question

Busco un algoritmo de búsqueda eficiente para obtener el más largamás corto patrón que se repite en una colección (~ 2 k de números enteros), donde se hace mi colección de solamente este patrón se repite (no hay ruido entre patrones repetidos), pero la última ocurrencia del patrón puede ser incompleta.

Ejemplos: que tengo: [2,4,1, 2,4,1, 2,4,1, 2,4,1, 2,4,1]
que me gustaría Recieve: [2,4,1]

tengo: [21,1,15,22, 21,1,15,22, 21,1,15,22, 21,1,15]
me gustaría Recieve: [21,1,15,22]

tengo: [3,2,3,2,5]
me gustaría para recibir: [] (no hay un patrón)

(espacios agregados solo para legibilidad)

Answer 1

El algoritmo muy directa sería así (en Python, pero no debería ser problema de traducir a Javascript):

def check(a, width): 
    '''check if there is a repeated pattern of length |width|''' 
    for j in range(width, len(a)): 
    if a[j] != a[j-width]: 
     return False 
    return True 

def repeated(a): 
    '''find the shortest repeated pattern''' 
    for width in range(1, len(a)): 
    if check(a, width): 
     return a[:width] 
    return [] 

Esto también debería ser bastante eficiente, ya que la mayoría de las veces el bucle en check() volverá a la derecha en la primera iteración, de modo que básicamente solo iterarás sobre la lista una vez.

Answer 2

Intente construir su agrupación inicial comenzando por el principio agregando un número al grupo hasta que llegue a un número que es el mismo que el primero en el grupo (el número anterior termina el patrón). Use esto como su patrón de prueba y siga, haciendo coincidir el patrón hasta que obtenga una falla. Si coincide con la colección completa (con su manejo especial de patrón final) ese es un candidato. Vuelve al lugar donde encontraste tu coincidencia inicial, luego continúa construyendo tu grupo hasta llegar a otro número que coincida con el primero en tu patrón. Repita, reemplazando a su candidato cada vez que encuentre uno más largo. Cuando su patrón tiene la misma longitud que la detención de recolección (esta no coincide). Si tiene un candidato que será el patrón más largo.

Answer 3

Creo que podría abordar este problema teniendo en cuenta el período del patrón. El período de una secuencia A [] es el número entero T más pequeño, tal que A [i + T] = A [i] para todo i. En su caso, cuando encuentre el período T, habrá terminado, ya que A [0..T-1] es el patrón más corto que está buscando. Por lo tanto, comience con un período posible mínimo T = 1 y pruebe si la secuencia satisface la propiedad periódica. En caso afirmativo, terminaste (esto solo ocurre cuando todos los elementos son idénticos). Para cualquier T más grande, debe probar si A [i + T] = A [i] para i = 0..A.len-T-1. Esto es solo un simple bucle.

Answer 4

Puede optimizar su búsqueda observando que la longitud de su colección debe ser un múltiplo de la longitud de su patrón. Si su colección tiene un tamaño que es primo, la única longitud de patrón posible es 1, es decir, ¡todos los elementos deben ser idénticos!