Finding Palidrome aus einer Permutation in Python

Question

Ich habe eine Zeichenfolge, ich muss herausfinden, palindromic sub-string of length 4 (all4 indexes Sub-Zeichenfolgen), in denen die Indizes in ascending order (index1<index2<index3<index4) sein sollten. Mein Code funktioniert gut für kleine Zeichenfolge wie mystr. Aber wenn es um große Saiten geht, braucht es viel Zeit.

from itertools import permutations 
    #Mystr 
    mystr = "kkkkkkz" #"ghhggh" 
    #Another Mystr 
    #mystr = "kkkkkkzsdfsfdkjdbdsjfjsadyusagdsadnkasdmkofhduyhfbdhfnsklfsjdhbshjvncjkmkslfhisduhfsdkadkaopiuqegyegrebkjenlendelufhdysgfdjlkajuadgfyadbldjudigducbdj" 
    l = len(mystr) 
    mylist = permutations(range(l), 4) 
    cnt = 0 
    for i in filter(lambda i: i[0] < i[1] < i[2] < i[3] and (mystr[i[0]] + mystr[i[1]] + mystr[i[2]] + mystr[i[3]] == mystr[i[3]] + mystr[i[2]] + mystr[i[1]] + mystr[i[0]]), mylist): 
     #print(i) 
     cnt += 1 
    print(cnt) # Number of palindromes found 

Answer 1

Wenn Sie mit der Grundstruktur des aktuellen Algorithmus halten wollen, ein paar Möglichkeiten, es zu beschleunigen, wäre combinations anstelle des permutations zu verwenden, die eine iterable in sortierter Reihenfolge angezeigt werden können. Dies bedeutet, dass Sie nicht überprüfen müssen, ob die Indizes aufsteigend sortiert sind. Zweitens können Sie das Bit, das nach einem Palindrom sucht, beschleunigen, indem Sie einfach prüfen, ob die ersten beiden Zeichen identisch mit den letzten zwei umgekehrten Zeichen sind (anstatt das Ganze gegen sein umgekehrtes Selbst zu vergleichen).

from itertools import combinations 
mystr = "kkkkkkzsdfsfdkjdbdsjfjsadyusagdsadnkasdmkofhduyhfbdhfnsklfsjdhbshjvncjkmkslfhisduhfsdkadkaopiuqegyegrebkjenlendelufhdysgfdjlkajuadgfyadbldjudigducbdj" 
cnt = 0 
for m in combinations(mystr, 4): 
    if m[:2] == m[:1:-1]: cnt += 1 
print cnt 

Oder wenn Sie das letzte Bit einem Einzeiler vereinfachen wollen:

print len([m for m in combinations(mystr, 4) if m[:2] == m[:1:-1]]) 

ich keine Echtzeit-Test auf das zu tun hat, sondern auf meinem System dieses Verfahren dauert etwa 6,3 Sekunden zu laufen (mit Ihrer wirklich langen Saite), die wesentlich schneller ist als Ihre Methode.