Solving Anagrams in Ruby
Someone posted a question on comp.lang.ruby recently asking for help with solving anagrams. The poster originally asked about ways of generating permutations and several people pointed him to the facets library which has some permutation utility functions. As it turns out, I benchmarked the following naive permutation generator as 3 times faster than the facets library code:
def words chars, result='', &b if chars.empty? yield result else chars.length.times do |i| c = (x = chars.clone).slice!(i) words(x, result + c, &b) end end end
However, generating all possible combinations of letters in an anagram is a very bad approach which doesn’t take into consideration key knowledge about the problem. Rather than generating all permutations of an anagram, which is infeasible for longer words, we can precompute a hash from our dictionary by using the sorted letters of words as keys. Then to solve an anagram, we simply sort the letters in the anagram and look it up in the hash.
The first program creates the hash and serializes it to disk for future anagram solving:
words = Hash.new() File.open("/usr/share/dict/words", "r") do |file| while line = file.gets word = line.chomp words[word.split('').sort!.join('')] += [word] end end File.open("word_hash", "w") do |file| Marshal.dump(words, file) end
The second program loads the serialized hash from disk to solve anagrams that we type at the console:
words = nil File.open("word_hash", "r") do |file| words = Marshal.load(file) end while true print "Enter word: " anagram = gets.chomp sorted_anagram = anagram.split('').sort!.join('') p words[sorted_anagram] end
This is really fast, but there are probably better methods. If you have one, feel free to add a comment with the code.