calculate........recursion(python)程序需要很长时间
calculate........recursion(python)程序需要很长时间
提问于 2015-06-02 07:38:33
我的程序需要很长时间来查找文件中的所有词汇表，以便打印所有可以创建的单词。如何通过不使用任何导入来使其读得更快？顺便说一句，我对python还不熟悉(例如，我在一个文件中包含的单词超过了4000+语音/字母/单词，如果您输入了任何字母，它将在该文件中找到所有可能的结果。
if the user enter: a c t b它将显示：(假设4000+中的所有三个字母/单词都在可以创建的文件中)
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)回答 1
Stack Overflow用户
回答已采纳
发布于 2015-06-02 07:56:07
似乎你想要生成所有可以由给定字母创建的排列，然后检查它们是否与某个字典中的“真实”单词相对应，就像查找在拼字游戏中可以创建的单词一样。
只需将参数中的字母交换到递归调用中，就可以使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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/30590116
复制相关文章
相似问题
腾讯云开发者
