Deciphering Python word unscrambler

Question

I'm currently trying to dig deep into python and I have found a challenge on (hackthissite.org) that I'm trying to crack. I have to unscramble 10 words that are found in the provided wordlist.

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()

The function permutation looks like it is the block of code that actually does the deciphering. Can you help me understand how it programatically is solving this?

Answer 1

The pseudocode for that looks something like:

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.

The dictionary() function is populating your word list from a file.

The permutation() function returns every permutation of letters in a given word.

---

The permutation() function is doing the following:

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

s[1:] returns the string with the first character truncated. You'll see that it uses recursion to call permutation() again until there are no characters left to be truncated from the front. You must know recursion to understand this line. Using recursion allows this algorithm to cover every number of letters and still be elegant.

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

For each letter position remaining.

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

Generate the permutation by moving the first letter (which we truncated earlier) to each of the positions between every other letter.

---

So, take the word "watch" for example. After recursion, there will be a loop that generates the following words:

awtch atwch atcwh atchw

All I did to generate those words was take the first letter and shift its position. Continue that, combined with truncating the letters, and you'll create every permutation.

(wow, this must be my longest answer yet)

Answer 2

There is a much better solution. This code is highly inefficient if there are many long words. A better idea is to sort lexicographically all each word in the dictionary, so that 'god' becomes 'dgo' and do the same for scrambled word. Then it's O(nlogn) for each word instead of O(n!)