从 Python 中的排列查找回文

Question

我有一个字符串，我需要找出palindromic sub-string of length 4（all 4 indexes个子字符串），其中索引应该在ascending order (index1<index2<index3<index4)。我的代码适用于像 mystr 这样的小字符串。但是当涉及到大字符串时，需要很长时间。

   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

如果您想坚持使用当前算法的基本结构，可以使用 combinations 而不是 permutations 来加快速度，这将 return 一个按排序顺序的可迭代对象。这意味着您不需要检查索引是否按升序排列。其次，您可以通过简单地检查前两个字符是否与反转的最后两个字符相同（而不是将整个事物与其反转的自我进行比较）来加快检查回文的位。

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

或者，如果您想将最后一点简化为一行：

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

我没有对此进行实时测试，但在我的系统上，此方法需要大约 6.3 秒才能达到运行（使用您的非常长的字符串），这比您的方法快得多。

从 Python 中的排列查找回文

Finding Palidrome from a permutation in Python

python

algorithm

permutation

palindrome