python 中的 Anagram 算法

Question

这个程序的功能就像一个字谜，下面的部分展示了一个小算法，它遍历存储在名为 word_list 的列表中的给定单词列表，并将其中的项目与 choice 用户插入的单词。

第一个循环遍历列表中的每一项并将它们分配给 word 然后设置 shared_letters（计数器决定字母 word 是否可以在开始遍历两个单词之间的共享字母之前，在 choice) 中找到的内容归零，以免在第二个循环期间溢出 i 可迭代对象。

第二个循环使用 word length 中存储的 word 的长度迭代 x 。然后循环通过条件 if 语句，该语句决定 sliced word 的 x 索引字母（正好等于 list(word)）是否在 sliced choice 中找到（list(choice)).如果是，则计数器 shared_letters 加 1，否则它会跳出第二个循环并返回到第一个循环以获取新单词。

循环过程在我之前运行良好，但出于某种原因在这段代码中它根本不再运行第二个循环，我尝试放入 print 语句来检查程序正在执行的路线，它总是跳过嵌套的 for 循环。即使当我尝试将它变成类似函数的东西时，程序也拒绝执行该函数。


choice = input("Enter a word: ") # User enters a word

# Algorithm below compares the entered word with all the words found in the dictionary, then saves any words found into "sushi" list

for i in range(num_words):      # Word loop, gives iterated word
  word = word_list[i]           # Picks a loop
  shared_letters = 0            # Resets # of shared letters
  for x in range(word_length):  # Goes through the letters of iterated word
    if sliced_word[x] in sliced_choice:  
      shared_letters = x + 1
    elif sliced_word[x] not in sliced_choice:
      break

这是完整的程序，以防万一您想更好地了解它，抱歉，如果编码看起来很混乱，我已经对这个程序进行了很多尝试，但我似乎从未达到很好的解决方案。


word_list = ["race","care","car","rake","caring","scar"]
sushi = []

word = ""
sliced_word = list(word)
word_length = len(sliced_word)
  
  
choice_word = ""
sliced_choice = list(choice_word)
choice_length = len(sliced_choice)

shared_letters = 0
num_words = len(word_list)

next_word = False

choice = input("Enter a word: ") # User enters a word 

# Algorithm below compares the entered word with all the words found in the dicitionary, then saves any words found into "sushi" list

for i in range(num_words):  # Word loop, gives iterated word
  word = word_list[i]      # Picks a loop
  shared_letters = 0      # Resets # of shared letters
  for x in range(word_length):  # Goes through the letters of iterated word
    if sliced_word[x] in sliced_choice:  
      # Checks if the letters of the iterated word can be found in the choice word 
      shared_letters = x + 1
      
    elif sliced_word[x] not in sliced_choice:
      break # If any of the letters within the iterated word are not within the choice word, it moves onto the next word
  
  if shared_letters == word_length:
    sushi.append(word_list[i])  
    # If all of the letters within the iterated word are found in the choice word, it appends the iterated word into the "sushi" list. Then moves onto the next word in the word_list.

Answer 1

您有很多问题，但我认为最大的问题是此搜索没有考虑具有多个相同字母的字谜。确定一个单词是否是变位词的最简单方法是查看它们每个字母的计数是否相同。

collections 模块中有一个名为 Counter 的内置助手 class 可以帮助解决此问题。

>>> from collections import Counter
>>> Counter("care")
Counter({'c': 1, 'a': 1, 'r': 1, 'e': 1})
>>> Counter("race")
Counter({'r': 1, 'a': 1, 'c': 1, 'e': 1})
>>> Counter("care") == Counter("race")
True

将此应用到您的示例中，您可以像这样重构：

word_list = ["race","care","car","rake","caring","scar"]
sushi = []

for word in word_list:
    if Counter(choice) == Counter(word):
        sushi.append(word)

如果我们必须一遍又一遍地创建 Counter 对象，这会有点慢，所以您可以选择将它们存储在字典中：

word_list = ["race","care","car","rake","caring","scar"]
word_counters = {word: Counter(word) for word in word_list}
sushi = []

for word, counter in word_counters.items():
    if Counter(choice) == counter:
        sushi.append(word)

如果你想找到一个不完美的匹配，比如一个词包含在另一个词中，你可以使用 - 运算符并测试左侧是否有任何字母留在后面：

>>> not (Counter("race") - Counter("racecar"))
True
>>> not (Counter("race") - Counter("bob"))
False

回到示例中：

word_list = ["race","care","car","rake","caring","scar"]
word_counters = {word: Counter(word) for word in word_list}
sushi = []

for word, counter in word_counters.items():
    if not (Counter(choice) - counter):
        sushi.append(word)

python 中的 Anagram 算法

Anagram algorithm in python

python

debugging

for-loop

if-statement

python-3.x