时间戳

首页 > 解决方案 > 查找所有可以从字母列表中组成的英语单词，使用每个字母的次数不超过它在列表中出现的次数

python - 查找所有可以从字母列表中组成的英语单词，使用每个字母的次数不超过它在列表中出现的次数

问题描述

我正在尝试将随机字母集输入到一个函数中，以便它从文本文件中返回所有可能的单词，这些单词可以由这些随机字母组成，长度在 4 到 9 个字符之间。目前，代码返回仅由集合中的字母组成的单词，但在某些情况下，它会多次使用一个元素来组成一个单词。我希望它只输出使用每个字母一次的单词。例如 'animal' 将被返回，但它使用了字母 'a' 两次来组成这个词。

letterList = ["a", "n", "i", "b", "s", "l", "s", "y", "m"] 

with open('american-english') as f:
    for w in f:
        w = w.strip()
        cond = all(i in letterList for i in w) and letterList[4] in w
        if 9 > len(w) >= 4 and cond:
            print(w)

标签： python

解决方案

一个简单的选择可能是使用您现有的方法比较每个字母的数量。

您还可以尝试使用 itertools.permutations 从您的字母中生成所有可能的“单词”，并检查每个单词是否都在字典中。我怀疑这会很慢，因为排列的数量会很大，而且大多数都不是单词。

查找字谜的常用技术是按字母顺序对两个单词的字母进行排序，然后进行相等比较：

sorted(word1)==sorted(word2)

如果这是 True，则 word1 和 word2 是字谜。您可以使用它来减少比较次数，因为使用此技术您只需要排序后唯一的排列。

我编写了一个脚本来显示所有三个工作并允许您对它们进行基准测试。我的测试表明，随着字母列表变长，未优化的 itertools 方法的扩展性非常差。计数方法一般，但精炼的 itertools 方法通常最快。当然，这些都可以进一步优化。和他们一起去吧。

import time
import itertools

letterList = list('catd')

#letter counting method
tic=time.time()
with open(r'D:/words_alpha.txt','r') as f:
    for word in f:
        if all([word.strip().count(letter) <= letterList.count(letter) for letter in word]):
            print(word.strip())
toc=time.time()
print(toc-tic)

#permutations with no refinement
tic=time.time()
with open(r'D:/words_alpha.txt','r') as f:
    for word in f:
        for n in range(1,len(letterList)+1):
            for pseudoword in itertools.permutations(letterList,n):
                if word.strip() == "".join(pseudoword):
                    print(word.strip())
toc=time.time()
print(toc-tic)

#permutations with anagram refinement
tic=time.time()
pwords=[]
for n in range(1, len(letterList) + 1):
    for pseudoword in itertools.permutations(letterList, n):
        if sorted(pseudoword) == list(pseudoword):
            pwords.append("".join(pseudoword))
print (pwords)
with open(r'D:/words_alpha.txt', 'r') as f:
    for word in f:
        if "".join(sorted(word.strip())) in pwords:
            print(word.strip())
toc=time.time()
print(toc-tic)

推荐阅读