Python-可能会给定输入字母的英文单字词字母。

我知道以前已经询问过这种方法的变体,但是我无法理解任何以前的实现,因为它们大多数涉及使用集和issubset方法。 这是我要尝试的操作:我在词典中有一组单词和可能的字母列表。我想确定是否可以通过重新排列列表中的字母来组成集合的成员。这是我当前的实现:
def solve(dictionary, letters):

    for word in dictionary: #for each word in the dictionary
        if len(word) > len(letters):   # first optimization, doesn\'t check words that are larger than letter set
            continue
        else: 
            scrambledword = \"\".join([b for b in sorted(list(word))]) #sorts the letters in each word
            if set(scrambledword).issubset(letters):
                print word


def main():
    dictionary = set([x.strip() for x in open(\"C:\\\\Python27\\\\dictionary.txt\")])        
    letters = sorted([\'v\',\'r\',\'o\',\'o\',\'m\',\'a\',\'b\',\'c\',\'d\'])
    solve(dictionary, letters)


main()
此实现的明显问题是,会发现某些单词在“字母”中使用多个字母。例如,单词“'cardboard \'显示为有效单词,尽管只有\\的一个副本。字母列表中的“ a \”和\“ r \”。如何在列表上使用\“ issubset \”方法?     
已邀请:
        要知道您是否可以用一组字母来做一个单词[哎呀,我自己做的-我的意思是'collection \'!],您希望每个字母至少出现正确的次数,所以我认为我们将不得不以某种方式处理其中的计数。根据定义,Python集合并不关心源列表中的元素数量。也许像
from collections import Counter

letters = [\'v\',\'r\',\'o\',\'o\',\'m\',\'a\',\'b\',\'c\',\'d\']
words = \'cardboard boom booom\'.split()
letterscount = Counter(letters)

for word in words:
    wordcount = Counter(word)
    print word, all(letterscount[c] >= wordcount[c] for c in wordcount)
给予
cardboard False
boom True
booom False
Counter是一个方便的实用程序类:
>>> c = Counter(letters)
>>> c
Counter({\'o\': 2, \'a\': 1, \'c\': 1, \'b\': 1, \'d\': 1, \'m\': 1, \'r\': 1, \'v\': 1})
>>> c[\'o\']
2
>>> c[\'z\']
0
[DSM:退货!我删除了一个社区编辑,因为该计数器实例不可散列,因此无法进行社区编辑。] 如果需要考虑搜索速度,则可以权衡一下内存和预计算时间:
from collections import defaultdict, Counter
from itertools import combinations

# precomputations
allwords = open(\'/usr/share/dict/words\').read().split() 
allwords = list(w for w in allwords if len(w) >= 3) # hack, /words contains lots of silliness
allwords_by_count = defaultdict(list)
for i, word in enumerate(allwords):
    allwords_by_count[frozenset(word)].append((word, Counter(word)))
    if i % 1000 == 0:
        print i, word


def wordsfrom(letters, words_by_count):
    lettercount = Counter(letters)
    for subsetsize in range(1, len(lettercount)+1):
        for subset in combinations(lettercount, subsetsize):
            for possword, posswordcount in words_by_count[frozenset(subset)]:
                if all(posswordcount[c] <= lettercount[c] for c in posswordcount):
                    yield possword

>>> wordsfrom(\'thistles\', allwords_by_count)
<generator object wordsfrom at 0x1032956e0>
>>> list(wordsfrom(\'thistles\', allwords_by_count))
[\'ess\', \'sis\', \'tit\', \'tst\', \'hei\', \'hie\', \'lei\', \'lie\', \'sie\', \'sise\', \'tie\', \'tite\', \'she\', \'het\', \'teth\', \'the\', \'els\', \'less\', \'elt\', \'let\', \'telt\', \'set\', \'sett\', \'stet\', \'test\', \'his\', \'hiss\', \'shi\', \'sish\', \'hit\', \'lis\', \'liss\', \'sil\', \'lit\', \'til\', \'tilt\', \'ist\', \'its\', \'sist\', \'sit\', \'shies\', \'tithe\', \'isle\', \'sile\', \'sisel\', \'lite\', \'teil\', \'teli\', \'tile\', \'title\', \'seit\', \'sesti\', \'site\', \'stite\', \'testis\', \'hest\', \'seth\', \'lest\', \'selt\', \'lish\', \'slish\', \'hilt\', \'lith\', \'tilth\', \'hist\', \'sith\', \'stith\', \'this\', \'list\', \'silt\', \'slit\', \'stilt\', \'liesh\', \'shiel\', \'lithe\', \'shiest\', \'sithe\', \'theist\', \'thesis\', \'islet\', \'istle\', \'sistle\', \'slite\', \'stile\', \'stilet\', \'hitless\', \'tehsil\', \'thistle\']
[呵呵。我只是注意到\ thistles \'本身不在列表中,但这是因为它不在word文件中。 是的,单词文件中确实有明显的“ nonwords”:
>>> assert all(w in allwords for w in (wordsfrom(\'thistles\', allwords_by_count)))
>>> 
    
        如果您寻找字谜,换句话说,您想重新排列,但要全部使用(而不是仅使用一个子集),那么还有另一种解决方案。 您首先要预处理字典中的所有单词。给定一个单词,您将产生用相同字母但按字母顺序排列的单词:
def alphabetize(word):
    \"\".join(sorted(word))
并将这些新单词放在一组
newDictionary
中 然后,您的函数可以对字母调用字母顺序,并检查结果是否在字典中。
def solve(newDictionary, letters):
    query = alphabetize(letters)
    return query in newDictionary
字母顺序功能是字谜的一个特征:当且仅当两个单词应用字母顺序产生相同的结果时,它们才是彼此的字谜。     
        导入“ 9”,我们定义了一个可哈希的多集:
def Letters(x):
    return frozenset(Counter(x).items())
现在,我们将词汇表预处理为字母-> {anagram1,anagram2,...}的字典:
vocabulary = [\'apple\', \'banana\', \'rats\', \'star\', \'tars\']
countsToWords = defaultdict(lambda: set())
for word in vocabulary:
    countsToWords[Letters(word)].add(word)
您的\'solve \'函数现在需要O(1)时间:
def solve(query):
    return countsToWords[Letters(query)]
例:
print( solve(\'star\') )
# {\'tars\', \'star\', \'rats\'} 
    

要回复问题请先登录注册