python - 程序需要很长时间来计算......递归(python)

Question

我的程序需要很长时间来查找文件中的所有词汇列表，以便打印可以创建的所有可能的单词。如何在不使用任何导入的情况下使其读取速度更快？顺便说一句，我是 python 新手:(例如，我在 1 个文件中包含超过 4000 个词汇/字母/单词如果您输入任何字母，它将在该文件中找到所有可能的结果。

if the user enter: a c t b

它将显示:(假设 4000 多个字母/单词中的所有这 3 个字母/单词都在可以创建的文件中)

ab
abc
act

这是我的程序

def scramble(r_letters, s_letters):
    """
    Output every possible combination of a word.
    Each recursive call moves a letter from
    r_letters (remaining letters) to
    s_letters (scrambled letters)
    """
    if len(r_letters) == 0:  # Base case: All letters used
        words.add(s_letters)
    else:  # Recursive case: For each call to scramble()
           # move a letter from remaining to scrambled
        for i in range(len(r_letters)):
            # Move letter to scrambled
            tmp = r_letters[i]
            r_letters = r_letters[:i] + r_letters[i+1:]
            s_letters += tmp

            scramble(r_letters, s_letters)

            # Put letter back in remaining letters
            r_letters = r_letters[:i] + tmp + r_letters[i:]
            s_letters = s_letters[:-1]
        if s_letters:
             words.add(s_letters)

Answer 1

您似乎想要生成可以从给定字母创建的所有排列，然后检查它们是否对应于某个字典中的任何“真实”单词，有点像查找可以在游戏中创建哪些单词拼字游戏。

只需将参数中的字母交换到递归调用，您就可以使您的 scramble 函数更快一些(并且更短)。这样，您就不必将它们交换回来:

def scramble(r_letters, s_letters):
    if s_letters:
        words.add(s_letters)
    for i in range(len(r_letters)):
        scramble(r_letters[:i] + r_letters[i+1:], s_letters + r_letters[i])

您也可以使用itertools.permutations为此，例如像这样，使用给定的字母生成不同字长的所有排列:

def scramble2(letters):
    for i in range(1, len(letters) + 1):
        for p in itertools.permutations(letters, i):
            words.add(''.join(p))

根据 IPython 的 %timeit，这比您的实现快大约三倍:

In [3]: %timeit test.scramble("test", "")
10000 loops, best of 3: 50.4 µs per loop
In [4]: %timeit test.scramble2("test")
100000 loops, best of 3: 16.7 µs per loop

<小时/>

但是，您根本不需要生成所有排列!只需计算单词中的字母并将其与您可用的字母数进行比较即可。您可以使用collections.Counter为此，或者创建您自己的类似计数器的字典。

import collections
letters = "abctk"
words = "cat back track tact".split()
letter_counts = collections.Counter(letters)
for word in words:
    word_counts = collections.Counter(word)
    if all(letter_counts.get(c, 0) >= n for c, n in word_counts.iteritems()):
        print word

这将打印“cat”和“back”

如果您想避免使用库(可以练习，但不要坚持这个习惯)，您可以创建自己的计数器，例如像这样:

def count(word):
    d = {}
    for c in word:
        d[c] = d.get(c, 0) + 1
    return d