itertools Stopp-Zeichen in einer Reihe Wiederholung

Question

ich den folgenden Code alle Strings von 20 Zeichen lang mit Kombinationen von A, T, G und C.

jedoch machen schrieb, würde ich mehr als 3 des vermeiden möchten gleiche Zeichen in einer Zeile, also habe ich eine if-Funktion hinzugefügt, um dies zu überprüfen. Das Problem ist, dass dies nach dem itertools Code ist, also ist es ein bisschen langsam. Ich frage mich, ob es eine Möglichkeit gibt, itertools zu verwenden, um dieses Ergebnis zu erzeugen, ohne itertools und dann eine if-Funktion ausführen zu müssen?

import sys 
import itertools 
import re 

x = ["A","T","G","C"] 
for i in itertools.product(x, repeat=20): 
     i = "".join(i) 
     if re.search(r"(\w)\1\1",i): 
       continue 
     else: 
       sys.stdout.write(i) 

Answer 1

Auf den ersten Blick scheint die Frage diese fragen zu werden:

Wie kann ich diese riesige Liste von Strings filtern, ohne den Schmerz, die zuerst die ganze Liste zu konstruieren?

Die Antwort darauf lautet: Sie tun es bereits! Die Dinge in itertools erzeugen träge erzeugte Sequenzen, die iterativ konstruiert werden. Ihr existierender Code ist also nicht und produziert eine enorme Liste von Milliarden von Strings.

Aber es gibt eine möglicherweise interessante Frage, die Sie fragen, fehlen könnte:

Wenn ich die Triplett-freie Saiten erzeugen, indem sie alle Fäden erzeugen, und diejenigen herausgefiltert werden mit Triolen, mein Code mit um zusätzliche Arbeit zu leisten, da die meisten der erzeugten Strings Drillinge enthalten. Angenommen, die Strings werden in lexikographischer Reihenfolge erzeugt; dann beginnen die ersten 4 ** 17 von ihnen mit AAA, und wir sollten wirklich in der Lage sein, all diese Dinge zu überspringen. Wie können wir es besser machen?

Leider, wenn Sie wollen, diese dann müssen Sie Ihren eigenen Code schreiben, es zu tun; itertools bietet diese Art von "pattern-filtered product" -Funktionalität nicht.

Es könnte wie folgt aussehen:

# generate all n-tuples with the property that their k-th element 
# is one of the things returned by successors(initial (k-1)-tuple). 
# So e.g. the first element is one of the things returned by 
# successors(()). 
def restricted_tuples(successors, n): 
    assert(n>=0) 
    if n==0: 
     for t in successors(()): yield (t,) 
    else: 
     for start in restricted_tuples(successors, n-1): 
      for t in successors(start): yield start+(t,) 

def successors_no_triples(start, alphabet): 
    if len(start)<2 or start[-1] != start[-2]: 
     for t in alphabet: yield t 
    else: 
     banned = start[-1] 
     for t in alphabet: 
      if t != banned: yield t 

print([''.join(x) for x in restricted_tuples(lambda start: successors_no_triples(start,'ABC'), 5)]) 

Die print am Ende nur illustrativ ist. Wenn Sie alle Milliarden Strings aus dem Fall des ursprünglichen Fragestellers ausdrucken möchten, sollten Sie besser die von restricted_tuples generierte Sequenz durchlaufen und sie einzeln stringifizieren und drucken.

Übrigens, die Anzahl der Länge-20-Sequenzen auf 4 Buchstaben mit dieser Eigenschaft ergibt sich 415.289.569.968. Sie werden eine Weile warten, wenn Sie versuchen, sie alle zu generieren, vor allem, wenn Sie wirklich wollen, mit jeder einzelnen tun.