Python: anagram查找器

Question

我有一个基字符串和一个带有特定单词的字典。我希望使用字典中的单词查找基字符串的所有可能的字谜。

例如：

base_string = 'Oscar Wilde'
words = {1: 'sidecar', 2: 'owl', 3: 'low', 4: 'acid', 5: 'bread', 6: 'slower'}

现在我想看看我能用字典里的单词做多少不同的字谜。希望输出的是‘侧角猫头鹰’，‘侧卡低’，‘酸慢’。

我将字符串转换为一个列表，如下所示：

letters = ['o', 's', 'c', 'a', 'r', 'w', 'i', 'l', 'd', 'e']

我希望我的代码所做的是检查字典中每个单词的组合。我有一个计数器来计数尝试过的组合的数量。

anagrams = []
counter = 0
for i in range(1, len(words)+1):
    anagram = ''
    for i in range(i+1, len(words)+1):
        if contain(letters, words[i]):  #if word is contained in the base string
            for i in words[i]:  #remove each letter of the word from the list of letters of the base string 
                letters.remove(i)
            anagram += words[i] + ' '
    if len(letters) >= 1:  #if all the letters are not used, it's not an anagram
        counter += 1
    if len(letters) == 0:  #if all the letters are used, it's an anagram
        anagrams.append(anagram)

print anagrams

def contain(list1, list2):
    counter1 = Counter(list1)
    counter2 = Counter(list2)
    for k in counter2:
        if counter2[k] != counter1.get(k):
            return False
    return True

findanagram()

我得到了KeyError的+= wordsi +‘’

我希望我已经解释得够清楚了。

Answer 1

我个人会推荐hege的解决方案。它简单，直截了当，切中要害。但是，如果您计划使用大型字典并多次重复此过程，则可能会对更快的方法感兴趣。

其思想是将每个字母与素数联系起来，即a= 2，b= 3，c= 5等。得到数字25的唯一方法是在单词中使用字母c两次。通过把一个单词中的所有字母相乘，你就可以得到它的id号。自然，这个词的任何字谜也会产生相同的id。

所以，您所要做的就是检查id的乘积，因为单词A和B等于您感兴趣的单词的id。

from itertools import combinations
from string import ascii_lowercase as alphabet

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
          47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
letter_id = dict(zip(alphabet, primes))

def get_word_id(word):
    product = 1
    for letter in word:
        product *= letter_id[letter]
    return product

words = ['sidecar', 'owl', 'low', 'acid', 'bread', 'slower']
dictionary = {}
for w in words:
    dictionary[w] = get_word_id(w)

base_string = 'Oscar Wilde'

for comb in combinations(words, 2):
    comb_id = 1
    for word in comb:
        comb_id *= dictionary[word]
    if get_word_id(base_string.replace(' ', '').lower()) == comb_id:
        print comb

正如我在hege的回答中所评论的那样，如果您感兴趣的不仅仅是对，您可以这样概括这些组合

for no_of_words in xrange(1, len(words)+1):
    for comb in combinations(words, no_of_words):
        ...