Ermitteln, ob die Sequenz ein Vielfaches einer Teilsequenz in Python ist

Ich habe ein Tupel von Nullen und Eins, zum Beispiel:

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

Es stellt sich heraus:

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

Ich wünsche eine Funktion f so dass, wenn s ein nicht leeres Tupel von Nullen und Eins ist, f(s) das kürzeste Subtupel r so dass s == r * n für eine positive ganze Zahl n .

So zum Beispiel,

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

Was ist eine glatte Möglichkeit, die Funktion f in Python zu schreiben?

Bearbeiten:

Die naive Methode, die ich derzeit benutze

 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] 

    7 Solutions collect form web for “Ermitteln, ob die Sequenz ein Vielfaches einer Teilsequenz in Python ist”

    Ich glaube, ich habe eine O (n) Zeit-Lösung (eigentlich 2n + r, n ist die Länge des Tupels, r ist sub tuplle), die keine Suffix-Bäume verwendet, sondern einen String-Matching-Algorithmus verwendet (wie KMP, den du finden solltest -das Regal).

    Wir verwenden den folgenden wenig bekannten Satz:

     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. 

    Ich behaupte nun, dass für die Zwecke unseres Problems bedeutet dies, dass alles, was wir tun müssen, ist festzustellen, ob die gegebene Tupel / Liste (oder String) ist eine zyklische Verschiebung von sich selbst!

    Um festzustellen, ob ein String eine zyklische Verschiebung von sich selbst ist, verknüpfen wir ihn mit sich selbst (es muss nicht einmal eine echte Concat sein, nur ein virtueller wird es tun) und nach einem Substring-Match (mit sich selbst) nachsehen.

    Für einen Beweis dafür ist die Saite eine zyklische Verschiebung von sich selbst.

    Wir haben die gegebene String y = uv = vu. Da uv = vu, müssen wir das u = z ^ k und v = z ^ l und damit y = z ^ {k + l} aus dem obigen Satz haben. Die andere Richtung ist leicht zu beweisen.

    Hier ist der Python-Code. Die Methode heißt 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() 

    Und hier ist der KMP-Code, den ich (wegen David Eppstein) benutzt habe.

     # 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 

    Für Ihre Probe gibt es diese Ausgänge

     [1,0,1,1] 

    wie erwartet.

    Ich verglich dies mit dem Code von shx2 (nicht der numpy), indem ich eine zufällige 50-Bit-String generiere, dann die Replikation, um die Gesamtlänge als 1 Million zu machen. Dies war die Ausgabe (die Dezimalzahl ist die Ausgabe von 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 

    Die oben genannte Methode dauerte ~ 4 Sekunden, während shx2's Methode dauerte ~ 21 Sekunden!

    Hier war der Zeitcode. (Shx2's Methode wurde Powercheck2 genannt).

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

    Die folgende Lösung ist O (N ^ 2), hat aber den Vorteil, keine Kopien (oder Scheiben) Ihrer Daten zu erstellen, da sie auf Iteratoren basieren.

    Abhängig von der Größe Ihrer Eingabe kann die Tatsache, dass Sie vermeiden, Kopien der Daten zu vermeiden, zu einer signifikanten Beschleunigung führen, aber natürlich würde es auch nicht für große Eingaben als Algorithmen mit geringerer Komplexität skalieren (zB O (N * LogN)).

    [Dies ist die zweite Revision meiner Lösung, die erste ist unten gegeben. Dies ist einfacher zu verstehen, und ist mehr entlang der Linien der OP-Tupel-Multiplikation, nur mit Iteratoren.]

     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 

    [Meine ursprüngliche Lösung]

     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 

    Sie können den Aufruf zum set() vermeiden, indem Sie so etwas wie:

     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 

    Und ersetzt diese Zeile:

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

    mit:

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

    Vereinfachung der Lösung von Knoothe Sein Algorithmus ist richtig, aber seine Umsetzung ist zu komplex. Diese Implementierung ist auch O (n).

    Da Ihr Array nur aus Einsen und Nullen besteht, bedarf es der vorhandenen str.find Implementierung (Bayer Moore), um die Idee von Knoothe zu implementieren. Es ist überraschend einfacher und erstaunlich schneller zur Laufzeit.

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

    Hier ist eine andere Lösung (im Wettbewerb mit meiner früheren iteratorbasierten Lösung), die numpy nutzt.

    Es macht eine (einzelne) Kopie Ihrer Daten, aber unter Ausnutzung der Tatsache, dass Ihre Werte 0s und 1s sind, ist es super-schnell, dank Numpys Magie.

     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 

    Nur ein anderer Ansatz für das Problem

    Ich stelle zuerst alle Faktoren der Länge fest und teile dann die Liste auf und prüfe, ob alle Teile gleich sind

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

    Sie können es in sublinearer Zeit durch XOR'ing die gedrehte Binärform für das Eingabefeld archivieren:

    1. input_binary die binäre Darstellung des Arrays, input_binary
    2. Loop von i = 1 to len(input_array)/2 und für jede Schleife das input_binary nach rechts um i Bits drehen, es als rotated_bin und dann den XOR von rotated_bin und input_binary .
    3. Das erste i , das 0 ergibt, ist der Index, zu dem der gewünschte Teilstring ist.

    Vollständiger Code:

     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] 

    Das ist nur ein dummer rekursiver Vergleich in Haskell. Es dauert etwa eine Sekunde für Knoothe's million long string (fa). Cooles Problem! Ich werde darüber nachdenken.

     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 
    Python ist die beste Programmiersprache der Welt.