从Python中的排列中查找Palidrome

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

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

来源

2016-07-23 Rasmi Ranjan Nayak

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

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秒运行（用你真正长的字符串），这比你的方法快得多。

来源

2016-07-23 23:17:40 bunji

我可以用其他方式加速吗？只要给我一个提示，我会尝试。 –

我建议阅读[this]（https://books.google.ca/books?id=9NdohJXtIyYC&lpg=PP1&ots=llc90BNZHd&dq=rytter+jewels+o&pg=PA111&redir_esc=y&hl=en#v=onepage&q&f=false）很好的分析一些可能会帮助你的算法。或者你可以找到一个关于寻找最长回文的算法的好教程（这里）（http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/），你可能会适应它为你的情况。目前你正在使用一种非常暴力的方法，所以改善你的算法是你最好的选择。 – bunji

你可以进一步节省一些毫秒m == m [:: - 1] 在左手边节省一些计算 –

从Python中的排列中查找Palidrome

回答

相关问题