Detectar si la secuencia es un múltiplo de una subsecuencia en Python

Tengo una tupla de ceros y unos, por ejemplo:

(1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1) 

Resulta:

 (1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1) == (1, 0, 1, 1) * 3 

Quiero una función f tal que si s es una tupla no vacía de ceros y unos, f(s) es el subtítulo más corto r tal que s == r * n para algún entero positivo n .

Así, por ejemplo,

 f( (1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1) ) == (1, 0, 1, 1) 

¿Cuál es una forma sencilla de escribir la función f en Python?

Editar:

El método ingenuo que estoy usando actualmente

 def f(s): for i in range(1,len(s)): if len(s)%i == 0 and s == s[:i] * (len(s)/i): return s[:i] 

Creo que tengo una solución de tiempo O (n) (en realidad 2n + r, n es la longitud de la tupla, r es subtipo) que no usa árboles de sufijos, pero usa un algoritmo de coincidencia de cadenas (como KMP, que debería encontrar desactivado). -el estante).

Utilizamos el siguiente teorema poco conocido:

 If x,y are strings over some alphabet, then xy = yx if and only if x = z^k and y = z^l for some string z and integers k,l. 

Ahora reclamo que, para los propósitos de nuestro problema, esto significa que todo lo que debemos hacer es determinar si la tupla / lista (o cadena) dada es un cambio cíclico de sí mismo.

Para determinar si una cadena es un cambio cíclico de sí misma, la concatenamos consigo misma (ni siquiera tiene que ser una concat real, solo una virtual lo hará) y verificamos una coincidencia de subcadena (consigo misma).

Para una prueba de eso, supongamos que la cadena es un cambio cíclico de sí misma.

El tenemos que la cadena dada y = uv = vu. Como uv = vu, debemos tener que u = z ^ k y v = z ^ l y, por tanto, y = z ^ {k + l} del teorema anterior. La otra dirección es fácil de probar.

Aquí está el código de python. El método se llama powercheck.

 def powercheck(lst): count = 0 position = 0 for pos in KnuthMorrisPratt(double(lst), lst): count += 1 position = pos if count == 2: break return lst[:position] def double(lst): for i in range(1,3): for elem in lst: yield elem def main(): print powercheck([1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1]) if __name__ == "__main__": main() 

Y aquí está el código KMP que utilicé (debido a David Eppstein).

 # Knuth-Morris-Pratt string matching # David Eppstein, UC Irvine, 1 Mar 2002 def KnuthMorrisPratt(text, pattern): '''Yields all starting positions of copies of the pattern in the text. Calling conventions are similar to string.find, but its arguments can be lists or iterators, not just strings, it returns all matches, not just the first one, and it does not need the whole text in memory at once. Whenever it yields, it will have read the text exactly up to and including the match that caused the yield.''' # allow indexing into pattern and protect against change during yield pattern = list(pattern) # build table of shift amounts shifts = [1] * (len(pattern) + 1) shift = 1 for pos in range(len(pattern)): while shift <= pos and pattern[pos] != pattern[pos-shift]: shift += shifts[pos-shift] shifts[pos+1] = shift # do the actual search startPos = 0 matchLen = 0 for c in text: while matchLen == len(pattern) or \ matchLen >= 0 and pattern[matchLen] != c: startPos += shifts[matchLen] matchLen -= shifts[matchLen] matchLen += 1 if matchLen == len(pattern): yield startPos 

Para su muestra esta salida

 [1,0,1,1] 

como se esperaba.

Comparé esto con el código de shx2 (no el numpy), generando una cadena aleatoria de 50 bits, luego la replicación para hacer la longitud total de 1 millón. Esta fue la salida (el número decimal es la salida de time.time ())

 1362988461.75 (50, [1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1]) 1362988465.96 50 [1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1] 1362988487.14 

El método anterior tomó ~ 4 segundos, mientras que el método de shx2 tomó ~ 21 segundos.

Aquí estaba el código de tiempo. (El método de shx2 fue llamado powercheck2).

 def rand_bitstring(n): rand = random.SystemRandom() lst = [] for j in range(1, n+1): r = rand.randint(1,2) if r == 2: lst.append(0) else: lst.append(1) return lst def main(): lst = rand_bitstring(50)*200000 print time.time() print powercheck(lst) print time.time() powercheck2(lst) print time.time() 

La siguiente solución es O (N ^ 2), pero tiene la ventaja de no crear copias (o porciones) de sus datos, ya que se basa en iteradores.

Dependiendo del tamaño de su entrada, el hecho de que evite hacer copias de los datos puede resultar en una aceleración significativa, pero, por supuesto, no se escalaría tan bien para entradas enormes como los algoritmos con menor complejidad (por ejemplo, O (N * logN)).

[Esta es la segunda revisión de mi solución, la primera se da a continuación. Este es más fácil de entender, y está más en la línea de la multiplicación de tuplas de OP, solo con iteradores.]

 from itertools import izip, chain, tee def iter_eq(seq1, seq2): """ assumes the sequences have the same len """ return all( v1 == v2 for v1, v2 in izip(seq1, seq2) ) def dup_seq(seq, n): """ returns an iterator which is seq chained to itself n times """ return chain(*tee(seq, n)) def is_reps(arr, slice_size): if len(arr) % slice_size != 0: return False num_slices = len(arr) / slice_size return iter_eq(arr, dup_seq(arr[:slice_size], num_slices)) s = (1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1) for i in range(1,len(s)): if is_reps(s, i): print i, s[:i] break 

[Mi solución original]

 from itertools import islice def is_reps(arr, num_slices): if len(arr) % num_slices != 0: return False slice_size = len(arr) / num_slices for i in xrange(slice_size): if len(set( islice(arr, i, None, num_slices) )) > 1: return False return True s = (1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1) for i in range(1,len(s)): if is_reps(s, i): print i, s[:i] break 

Puedes evitar la llamada a set() usando algo como:

 def is_iter_unique(seq): """ a faster version of testing len(set(seq)) <= 1 """ seen = set() for x in seq: seen.add(x) if len(seen) > 1: return False return True 

y reemplazando esta línea:

 if len(set( islice(arr, i, None, num_slices) )) > 1: 

con:

 if not is_iter_unique(islice(arr, i, None, num_slices)): 

Simplificando la solución de Knoothe. Su algoritmo es correcto, pero su implementación es demasiado compleja. Esta implementación también es O (n).

Como su matriz solo está compuesta de unos y ceros, lo que hago es usar la implementación existente de str.find (Bayer Moore) para implementar la idea de Knoothe. Es sorprendentemente más simple y sorprendentemente más rápido en tiempo de ejecución.

 def f(s): s2 = ''.join(map(str, s)) return s[:(s2+s2).index(s2, 1)] 

Aquí hay otra solución (compitiendo con mi solución anterior basada en iteradores), aprovechando numpy.

Hace una (única) copia de sus datos, pero aprovechando el hecho de que sus valores son 0 y 1, es súper rápido, gracias a las magias de numpy.

 import numpy as np def is_reps(arr, slice_size): if len(arr) % slice_size != 0: return False arr = arr.reshape((-1, slice_size)) return (arr.all(axis=0) | (~arr).all(axis=0)).all() s = (1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1) * 1000 a = np.array(s, dtype=bool) for i in range(1,len(s)): if is_reps(a, i): print i, s[:i] break 

Solo un enfoque diferente al problema

Primero determino todos los factores de la longitud y luego divido la lista y verifico si todas las partes son iguales

 >>> def f(s): def factors(n): #http://stackoverflow.com/a/6800214/977038 return set(reduce(list.__add__, ([i, n//i] for i in range(2, int(n**0.5) + 1) if n % i == 0))) _len = len(s) for fact in reversed(list(factors(_len))): compare_set = set(izip(*[iter(s)]*fact)) if len(compare_set) == 1: return compare_set >>> f(t) set([(1, 0, 1, 1)]) 

Puede archivarlo en tiempo sublineal haciendo XOR en el formato binario girado para la matriz de entrada:

  1. obtener la representación binaria de la matriz, input_binary
  2. bucle de i = 1 to len(input_array)/2 , y para cada bucle, gire el input_binary a la derecha en i bits, guárdelo como rotated_bin , luego compare el XOR de rotated_bin y input_binary .
  3. La primera i que arroja 0, es el índice al que corresponde la subcadena deseada.

Código completo:

 def get_substring(arr): binary = ''.join(map(str, arr)) # join the elements to get the binary form for i in xrange(1, len(arr) / 2): # do ai bit rotation shift, get bit string sub_bin rotated_bin = binary[-i:] + binary[:-i] if int(rotated_bin) ^ int(binary) == 0: return arr[0:i] return None if __name__ == "__main__": test = [1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1] print get_substring(test) # [1,0,1,1] 

Esta es sólo una comparación recursiva tonta en Haskell. Se tarda aproximadamente un segundo para el millón de cuerdas largas de Knoothe (fa). Problema genial Lo pensaré un poco más.

 a = concat $ replicate 20000 [1,1,1,0,0,1,0,1,0,0,1,0,0,1,1,1,0,0, 0,0,0,0,1,1,1,1,0,0,0,1,1,0,1,1,1,1, 1,1,1,0,0,1,1,1,0,0,0,0,0,1] fs = f' s [] where f' [] result = [] f' (x:xs) result = let y = result ++ [x] in if concat (replicate (div (length s) (length y)) y) == s then y else f' xs y