Word Jumble Algorithm

Question

Given a word jumble (i.e. ofbaor), what would be an approach to unscramble the letters to create a real word (i.e. foobar)? I could see this having a couple of approaches, and I think I know how I'd do it in .NET, but I curious to see what some other solutions look like (always happy to see if my solution is optimal or not).

This isn't homework or anything like that, I just saw a word jumble in the local comics section of the paper (yes, good ol' fashioned newsprint), and the engineer in me started thinking.

edit: please post some pseudo code or real code if you can; it's always nice to try and expand language knowledge by seeing examples like this.

Answer 1

Create all the permutations of the string, and look them up in a dictionary.

You can optimize by looking up shorter strings that begin words, and if there are no words of suitable length in the dictionary that start with those strings, eliminating permutations starting with those letters from further consideration.

Answer 2

Have a dictionary that's keyed by the letters of each word in sorted order. Then take you jumble an sort the letters - look up all the words in the dictionary by that sorted-letter string.

So, as an example, the words 'bear' and 'bare' would be in the dictionary as follows:

key    word
-----  ------
aber    bear
aber    bare

And if you're given the jumble, 'earb', you'd sort the letters to 'aber' and be able to look up both possible words in the dictionary.

Answer 3

CodeProject has a couple of articles here and here. The second uses recursion. Wikipedia also outlines a couple of algorithms here. The Wikipedia article also mentions a program called Jumbo that uses a more heuristic approach that solves the problem like a human would. There seem to be a few approaches to the problem.

Answer 4

Depending on the length of the string WhirlWind's approach could be faster, but an alternative way of doing it which has more or less O(n) complexity is instead of creating all the permutations of the string and looking them up, you go through all the words in the dictionary and see if each can be built from the input string.

A really smart algorithm that knows the number of words in the dictionary in advance could do something like this:

sort letters in jumbled string
if factorial(length of jumbled string) > count of words in dictionary:
    for each word in dictionary:
       sort letters in dictionary word 
       if sorted letters in dictionary word == sorted letters in jumbled string:
           append original dictionary word to acceptable word list
else:
    create permutation list of jumbled letters
    for each permutation of letters:
        search in dictionary for permutation
        if permutation in dictionary:
            add word to acceptable word list

Answer 5

http://www.codeproject.com/KB/game/Anagrams2.aspx