2

我用 Python 编写了一个 Anagram 求解程序。我想听听你的意见，我是否做得对。让我解释一下逻辑：

  1. 首先，用户提供他/她希望为其生成单个单词字谜的两个单词的输入（2 个字符串值）
  2. 将两者连接起来，并导出第三个值。
  3. 第三个值由 itertools.permutations 函数处理，其中单词的所有可能排列都导出为列表。
  4. 该列表使用从列表派生的字符串值进行格式化。
  5. 至此，我打开了一个单词列表，将用作字典来比较字符串值是否为实际单词。
  6. 逐行读取文件并将字符串值与行进行比较。
  7. 如果找到匹配项，则程序在屏幕上将输出打印为字典匹配

请告诉我我是否正确地处理它或者是否可以提出任何改进建议。任何反馈表示赞赏。我是 Python 新手。

这是代码：

    #This program has been created to solve anagram puzzles

# All the imports go here
#import re
import itertools
import fileinput

def anaCore():
    print 'This is a Handy-Dandy Anagram Solving Machine'
    print 'First, we enter the first word....'
    anaWordOnly = False

    firstWord = raw_input('Please enter the first word > ')
    print 'Thank you for entering %r as your first word' % firstWord
    print 'Now we enter the second word....'
    secondWord = raw_input('Please enter the second word > ')
    print 'Thank you for entering %r as your second word' % secondWord

    thirdWord = firstWord+secondWord

    print thirdWord

    mylist = itertools.permutations(thirdWord)

    for a in mylist:
        #print a
        mystr = ''.join(a)
        for line in fileinput.input("brit-a-z.txt"):       
            if mystr in line:
                print 'Dictionary match found', mystr
        #print mystr

anaCore()
4

4 回答 4

1

你为什么要这样做mystr =''.join(a)？为什么不做mystr = a呢？

我认为这if mystr in line:也不对，因为您可以将 mystr 用作例如“dog”，将 line 用作“dogger bank”或类似的东西。您可能应该检查是否相等。

除此之外，我看不出有什么不妥。

如果你想聪明一点，你可以创建一个包含初始字典和字典 n - 1 中所有单词组合的第 2、3、4、...n 个字典。这样你也可以找到多词字谜。不要让 n 变得太大，否则字典会占用大量空间。

于 2011-07-27T17:27:24.477 回答
1

当然，您可以生成单词的所有排列。但是，我认为对 word 中的字母进行排序会更方便。因此，您必须对整个字典进行预处理，即对每个单词中的字母进行排序。然后，您只需要检查已排序的字符序列。

为了简化：我会生成你的字谜单词的排序序列。对于文件中的每一行，我会对它的字符进行排序并检查两者是否相同。如果是，请检查它们是否是相同的单词。如果它们不是相同的词，它们就是字谜。

于 2011-07-27T17:28:36.630 回答
1

我的一些想法：

当前的方法是首先生成“thirdWord”的所有可能排列，然后对于每个排列，您通过每次读取文本文件来检查它是否存在于字典中。

您不妨在程序开始时只阅读一次字典文件，将单词放入“集合”中。然后，您可以使用 'in' 轻松检查集合中是否存在排列：

>>> a = set(['hello','world','this','is','set'])
>>> 'hello' in a
True
>>> 'python' in a
False
>>>

此外，对于一些长的“第三个字”，它会产生太多的排列。例如，对于一个长度为 16 且包含所有不同字母的单词，它会生成 16！= 20,922,789,888,000 个排列。这有点大。

您可以通过迭代字典中的单词来反转该过程，并检查每个单词是否是带有“thirdWord”的字谜。对于更长的单词，这应该比检查所有排列更快。

检查字谜很简单：

>>> sorted('abc') == sorted('bca')
True
>>> sorted('aab') == sorted('xxx')
False
于 2011-07-27T17:41:55.910 回答
0

你的方法很好；在字符串上调用 itertools.permutations 是查找匹配项的好方法。这里只是一些想法/改进

  • mylist = itertools.permutations(thirdWord)：请记住，permutations它实际上并没有返回一个列表——它返回一个生成器，它消耗恒定数量的内存（相对于排列的数量）并根据需要产生新的排列。特别是，当您遍历生成器时，您一次会产生一个排列。此外，生成器只能产生正向值——您通常不能在生成器上向后迭代。生成器是 Python 中的一个关键概念。有关详细信息，请参阅http://wiki.python.org/moin/Generators。
  • 请记住，字符串比较区分大小写。假设你的字典文件是小写的，你应该小写你的输入。s.lower()返回字符串的小写副本s。
  • 您的字典查找算法效率低下。再看看你的循环。您的外部循环检查字符的每个排列，因此它将运行 n! 次，其中 n 是输入的长度。但是对于每一个排列，你都会再次读取文件中的每一行。如果您的字典中有 m 个单词，则您的程序需要 O(n!*m) 个工作。如果您只是将字典文件加载到 Pythonset中，那么查找每个排列的时间是 O(1)。所以你的总运行时间是 O(n!)。
于 2011-07-27T17:35:39.147 回答