如何优化这个 Python 程序来查找回文？

Question

我制作了这个 Python 程序，它从给定的单词列表中生成多单词回文。（回文是向前和向后读取相同的字符序列，忽略空格、标点符号和大写。）该程序采用列表指定长度范围的单词和形式组合（在每个组合的最小和最大单词数之间）。对于每个组合，它检查组合是否有效（有效意味着它是一个回文，并且至少包含两个不同的单词），然后将这些单词连接在一起形成一个文本。该程序通过删除非字母数字字符并将其转换为小写来清理组合文本。如果清理后的文本是回文，则将单词组合存储在找到的回文列表中。最后，该程序打印所有发现的回文，保持原始单词格式，单词之间有空格。问题是算法超级慢。即使只有 15 个单词，最小回文长度为 3，最大回文长度为 7，也需要四分钟多的时间。我怎样才能优化这段代码，使它不会花费那么长时间？

import itertools

def main():
    word_list = ['a', 'man', 'plan', 'canal', 'panama', 'the', 'of', 'and', 'to', 'in', 'is', 'you', 'that', 'it', 'he']
    min_words, max_words = 3, 7

    found_palindromes = []

    for n in range(min_words, max_words + 1):
        for combination in itertools.product(word_list, repeat=n):
            if len(set(combination)) > 1:
                combined_text = ''.join(combination)
                cleaned_text = ''.join(char for char in combined_text if char.isalnum()).lower()

                if cleaned_text == cleaned_text[::-1]:
                    found_palindromes.append(' '.join(combination))

    for palindrome in found_palindromes:
        print(palindrome)


if __name__ == "__main__":
    main()

我尝试稍微简化代码，删除不需要的功能，改进逻辑，但并没有太大帮助（时间只减少了大约 1%）。我不太擅长编码，所以我可能会遗漏一些明显的东西。

Answer 1

您可以使用基于不兼容的开始/结束单词和剩余长度差异的长度的一些短路的递归：

word_list = ['a', 'man', 'plan', 'canal', 'panama', 'the', 'of', 'and',
             'to', 'in', 'is', 'you', 'that', 'it', 'he']

def findPal(words, minLen=3, maxLen=7, prefix="", suffix="", addLeft=True):

    if prefix[:len(suffix)] != suffix[::-1][:len(prefix)]:
        return # mismatched on common start and end
    
    if not prefix and not suffix:
        words = sorted(words,key=len,reverse=True)
    if sum(map(len,words[:maxLen]))<abs(len(prefix)-len(suffix)):
        return # not enough words to fill difference
    
    for i,word in enumerate(words):
        combined = prefix+word+suffix
        if combined == combined[::-1] and len(set(combined))>1:
            if minLen <= 1: yield [word]
        if maxLen == 1: continue
        if addLeft:
            for left in findPal(words,minLen-1,maxLen-1,prefix,word+suffix,False):
                yield left + [word]
        else:
            for right in findPal(words,minLen-1,maxLen-1,prefix+word,suffix,True):
                yield [word] + right

输出：

for p in findPal(word_list):
    print(*p)

a man a panama
a man a panama man a panama
a a man a panama a