解读Python单词解码器

Question

我现在正在深入学习Python，发现了一个在(hackthissite.org)上的挑战，我正在努力解决。这个挑战要求我从提供的单词列表中解开10个单词的字谜。

def permutation(s):
    if s == "":
        return [s]
    else:
        ans = []
        for an in permutation(s[1:]):
            for pos in range(len(an)+1):
                ans.append(an[:pos]+s[0]+an[pos:])
        return ans

def dictionary(wordlist):
    dict = {}
    infile = open(wordlist, "r")
    for line in infile:
        word = line.split("\n")[0]
        # all words in lower case!!!
        word = word.lower()
        dict[word] = 1
    infile.close()
    return dict

def main():
    diction = dictionary("wordlist.txt")
    # enter all the words that fit on a line or limit the number
    anagram = raw_input("Please enter space separated words you need to unscramble: ")
    wordLst = anagram.split(None)

    for word in wordLst:
        anaLst = permutation(word)
        for ana in anaLst:
            if diction.has_key(ana):
                diction[ana] = word
                #print "The solution to the jumble is" , ana
    solutionLst = []
    for k, v in diction.iteritems():
        if v != 1:
            solutionLst.append(k)
            print "%s unscrambled = %s" % (v, k)
    print solutionLst

main()

看起来，permutation这个函数就是实际进行解密的代码块。你能帮我理解它是怎么通过编程来解决这个问题的吗？

Answer 1

我也为那个网站写了这段代码。下面是可以运行的代码：

def import_dictionary():
    dictionary = []
    try:
        file = open("C:\\Users\\Mason\\Desktop\\diction.txt", "r")#location of your dictionary or provided wordlist
        fileContents = file.readlines() #read text file and store each new line as a string
    finally:
        file.close()
    for i in range(len(fileContents)):
        dictionary.extend(fileContents[i].split()) #changes the list by removing \n's from line breaks in text file
    return dictionary

def import_scrambled_words():
    scrambledWords = []
    try:
        file = open("C:\\Users\\Mason\\Desktop\\scrambled.txt", "r") #location of your scrambled word file
        fileContents = file.readlines() #read text file and store each new line as a string
    finally:
        file.close()
    for i in range(len(fileContents)):
        scrambledWords.extend(fileContents[i].split()) #changes the list by removing \n's from line breaks in text file
    return scrambledWords

def unscramble_word(scrambledWord):
    countToMatch = len(scrambledWord)
    matchedWords = []
    string = ""

    for word in dictionary:
        count = 0
        for x in scrambledWord:
            if x in word:
                count += 1
            if count == countToMatch:
                matchedWords.append(word)
                break
    for matchedWord in matchedWords:
        if len(matchedWord) == len(scrambledWord):
            print(matchedWord)
            string = matchedWord
            break #this returns only one unscrambles word
    return string

if __name__ == '__main__':
    finalString = ""
    try:
        scrambled = import_scrambled_words()
        print(scrambled)
        dictionary = import_dictionary()
        for x in scrambled:
            finalString += unscramble_word(x)
            finalString +=", "
        len(finalString)

        print(finalString)

    except Exception as e:
        print(e)

这段代码会从一个保存的乱序单词文件中读取内容，然后和一个单词列表进行对比（我这边用的是字典，算是多做了一点）。为了在规定的30秒内完成挑战，我从hackThissite上复制了一些内容，然后粘贴到我的乱序单词文件里。保存后，运行程序，然后把从我的Python控制台输出的结果复制粘贴出来。

Answer 2

其实有个更好的办法。如果字典里有很多长单词，这段代码效率就很低。更好的想法是，把字典里的每个单词按字母顺序排序，比如把'god'变成'dgo'，然后对打乱的单词也做同样的处理。这样每个单词的处理时间就变成O(nlogn)，而不是O(n!)，效率高多了。

Answer 3

这个伪代码看起来大概是这样的：

Load the word list (dictionary)
Input the words to unscramble
For each word:
  Find every permutation of letters in that word (permutation)
  For each permutation:
    Add this permutation to the solution list if it exists in the dictionary
Print the solutions that were found.

dictionary() 函数是从一个文件中填充你的单词列表。

permutation() 函数会返回一个给定单词中所有字母的排列组合。

---

permutation() 函数的工作原理如下：

for an in permutation(s[1:]):

s[1:] 会返回去掉第一个字符后的字符串。你会看到它使用了递归，也就是说它会不断调用 permutation() 函数，直到前面没有字符可以去掉为止。要理解这一行，你需要知道什么是递归。使用递归可以让这个算法处理任意数量的字母，同时保持优雅。

for pos in range(len(an)+1):

对于每个剩下的字母位置。

ans.append(an[:pos]+s[0]+an[pos:])

通过将第一个字母（我们之前去掉的）移动到每个其他字母之间的每个位置来生成排列。

---

比如说，拿“watch”这个词举例。在递归之后，会有一个循环生成以下单词：

awtch
atwch
atcwh
atchw

我生成这些单词的方法就是把第一个字母的位置移动一下。继续这样做，再加上去掉字母，你就能创建出所有的排列组合。

（哇，这可能是我写过的最长的回答了）