Suchen Sie sich wiederholende Unterliste innerhalb der großen Liste

Question

Ich habe eine große Liste von Unterlisten (ca. 16000), die ich finden möchte, wo das sich wiederholende Muster beginnt und endet. Ich bin nicht 100% sicher, dass es eine Wiederholung gibt, aber ich habe einen starken Grund, dies zu glauben, aufgrund der Diagonalen, die in der Unterlistensequenz erscheinen. Die Struktur einer Liste von Unterlisten wird bevorzugt, da sie für andere Dinge in diesem Skript verwendet wird. Die Daten sieht wie folgt aus:

data = ['1100100100000010', 
     '1001001000000110', 
     '0010010000001100', 
     '0100100000011011', etc 

Ich habe keine Zeit Zwänge, aber die schnellste Methode, bei der nicht die Stirn runzeln würde. Der Code sollte in der Lage sein, die Anfangs-/Endsequenz und den Ort innerhalb der Liste zurückzugeben, um in der Zukunft aufgerufen zu werden. Wenn es eine Anordnung der Daten gibt, die nützlicher wäre, kann ich versuchen, sie bei Bedarf neu zu formatieren. Python ist etwas, was ich in den letzten Monaten gelernt habe, daher kann ich meine eigenen Algorithmen noch nicht einfach von Grund auf neu erstellen. Vielen Dank!

Answer 1

Hier ist ein ziemlich einfacher Code, der eine Zeichenkette nach benachbarten Wiederholungsuntersequenzen scannt. Setzen Sie minrun auf die Länge der kleinsten Untersequenzen, die Sie überprüfen möchten. Für jede Übereinstimmung gibt der Code den Startindex der ersten Teilsequenz, die Länge der Teilsequenz und die Teilsequenz selbst aus.

data = [ 
    '1100100100000010', 
    '1001001000000110', 
    '0010010000001100', 
    '0100100000011011', 
] 
data = ''.join(data) 

minrun = 3 
lendata = len(data) 
for runlen in range(minrun, lendata // 2): 
    i = 0 
    while i < lendata - runlen * 2: 
     s1 = data[i:i + runlen] 
     s2 = data[i + runlen:i + runlen * 2] 
     if s1 == s2: 
      print(i, runlen, s1) 
      i += runlen 
     else: 
      i += 1 

Ausgang

1 3 100 
4 3 100 
8 3 000 
15 3 010 
18 3 010 
23 3 000 
32 3 001 
38 3 000 
47 3 001 
53 3 000 
17 15 001001000000110 
32 15 001001000000110 

beachten Sie, dass die gleiche Sequenz der Länge 3 bei Index 15 und 18 = 15 + 3 erhalten: 010; Dies zeigt an, dass 3 benachbarte Kopien von 010 vorhanden sind. In ähnlicher Weise gibt es drei benachbarte Kopien der Sequenz mit dem Index 17 der Länge 15.