Python中的字谜代码 - 将动态生成的字符串与文本文件进行比较

Question

我写了一个用Python做的字谜程序，想听听你们的意见，看看我这样做对不对。让我来解释一下我的逻辑：

1. 首先，用户输入两个单词，这两个单词是我想生成一个字谜的基础（也就是两个字符串）。
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()

Answer 1

你的方法没问题；在字符串上使用itertools.permutations来找匹配是个不错的选择。这里有一些想法和改进建议。

• mylist = itertools.permutations(thirdWord)：记住，permutations并不是直接返回一个列表，而是返回一个生成器。这个生成器在内存使用上是固定的（和排列的数量有关），并且会根据需要生成新的排列。特别是，当你遍历这个生成器时，它一次只会生成一个排列。而且，生成器只能向前生成值，通常不能反向遍历。生成器是Python中的一个重要概念。想了解更多，可以查看http://wiki.python.org/moin/Generators。
• 记住，字符串比较是区分大小写的。如果你的字典文件是小写的，那么你输入的内容也应该转换成小写。s.lower()会返回字符串s的小写版本。
• 你的字典查找算法效率不高。再看看你的循环。外层循环检查每一种字符的排列，所以它会运行n!次，其中n是你输入的长度。但是对于每一个排列，你又要重新读取文件中的每一行。如果你的字典里有m个单词，那么你的程序需要O(n!*m)的工作量。如果你把字典文件加载到Python的set中，那么查找每个排列的时间就变成O(1)。这样，你的总运行时间就变成O(n!)了。

Answer 2

当然，你可以生成所有单词的排列组合。不过，我觉得把单词里的字母先排序会更方便。因此，你需要先处理一下整个字典，也就是把每个单词里的字母都排序。然后，你只需要检查字母的排序结果。

简单来说，我会先生成你想要的那个字的字母排序结果。然后，对于文件中的每一行，我会把它的字母也排序，然后检查这两个排序结果是否相同。如果相同，再检查它们是不是完全一样的单词。如果不是完全一样的单词，那它们就是变位词（anagrams）。

Answer 3

我有一些想法：

现在的做法是先生成所有可能的'thirdWord'的排列，然后对每一个排列，检查它是否在字典里，这个过程是每次都要读取文本文件。

其实你可以在程序开始的时候只读取一次字典文件，把单词放到一个'集合'里。这样的话，你就可以用'in'来轻松检查某个排列是否在这个集合里：

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

另外，如果'thirdWord'很长，就会生成太多的排列。例如，如果一个单词有16个不同的字母，它会生成16! = 20,922,789,888,000种排列。这数量可真是太庞大了。

你可以反过来做，遍历字典里的单词，检查每个单词是否和'thirdWord'是字母重排（即是否是变位词）。对于较长的单词，这种方法应该比检查所有排列要快。

检查变位词其实很简单：

>>> sorted('abc') == sorted('bca')
True
>>> sorted('aab') == sorted('xxx')
False