Python Algorithm - Jumble Solver [Closed]

Question

I'm writing a program to find all the possible combinations of a jumbled word from a dictionary in python.

Here's what I've wrote. It's in O(n^2) time. So, my question is Can it be made faster ?

import sys

dictfile = "dictionary.txt"

def get_words(text):
    """ Return a list of dict words """
    return text.split()


def get_possible_words(words,jword):
    """ Return a list of possible solutions """
    possible_words = []
    jword_length = len(jword)
    for word in words:
        jumbled_word = jword
        if len(word) == jword_length:
            letters = list(word)
            for letter in letters:
                if jumbled_word.find(letter) != -1:
                    jumbled_word = jumbled_word.replace(letter,'',1)
            if not jumbled_word:
                possible_words.append(word)
    return possible_words       


if __name__ == '__main__':
    words = get_words(file(dictfile).read())
    if len(sys.argv) != 2:
        print "Incorrect Format. Type like"
        print "python %s <jumbled word>" % sys.argv[0]
        sys.exit()
    jumbled_word = sys.argv[1]
    words = get_possible_words(words,jumbled_word)
    print "possible words :"
    print '\n'.join(words)

Accepted Answer

The usual fast solution to anagram problems in to build a mapping of sorted letters to a list of the unsorted words.

With that structure in-hand, the lookups are immediate and fast:

def build_table(wordlist):
    table = {}
    for word in wordlist:
        key = ''.join(sorted(word))
        table.setdefault(key, []).append(word)
    return table

def lookup(jumble, table):
    key = ''.join(sorted(jumble))
    return table.get(key, [])

if __name__ == '__main__':

    # Build table
    with open('/usr/share/dict/words') as f:
        wordlist = f.read().lower().split()
    table = build_table(wordlist)

    # Solve some jumbles
    for jumble in ['tesb', 'amgaarn', 'lehsffu', 'tmirlohag']:
        print(lookup(jumble, table))

Notes on speed:

The lookup() code is the fast part.
The slower buildtable() function is written for clarity.
Building the table is a one-time operation.
If you care about run-time across repeated runs, the table should be cached in a text file.

Text file format (alpha-order first, followed by the matching words):

   aestt state taste tates testa
   enost seton steno stone
   ...

With the preprocessed anagram file, it becomes a simple matter to use subprocess to grep the file for the appropriate line of matching words. This should give a very fast run time (because the sorts and matches were precomputed and because grep is so fast).

Build the preprocessed anagram file like this:

with open('/usr/share/dict/words') as f:
    wordlist = f.read().split()

table = {}
for word in wordlist:
    key = ''.join(sorted(word)).lower()
    table[key] = table.get(key, '') + ' ' + word

lines = ['%s%s\n' % t for t in table.iteritems()]
with open('anagrams.txt', 'w') as f:
    f.writelines(lines)

Answer 2

I was trying to solve using ruby -

Answer 3

alter the getwords to return a dict(). Make each key have a value of true or 1

import itertools and use itertools.combinations to make all possible anagramatic strings from the "jumbled_word"

then loop over the possible strings checking if they are keys in the dict

if you wanted a DIY algorithm solution then loading the dictionary into a tree might be "better" but I doubt in the real world that it would be faster

Python Algorithm - Jumble Solver [Closed]

Must Read

3 Answers

Marcus Vance