Lojic Technologies

Solving Anagrams in Ruby

with 4 comments

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
    chars.length.times do |i|
      c = (x = chars.clone).slice!(i)
      words(x, result + c, &b)

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]

File.open("word_hash", "w") do |file|
  Marshal.dump(words, file)

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)

while true
  print "Enter word: "
  anagram = gets.chomp
  sorted_anagram = anagram.split('').sort!.join('')
  p  words[sorted_anagram]

This is really fast, but there are probably better methods. If you have one, feel free to add a comment with the code.

Written by Brian Adkins

October 22, 2007 at 7:53 pm

Posted in programming

Tagged with , ,

4 Responses

Subscribe to comments with RSS.

  1. Very smart, small and clean code. I would just add .downcase to gets.chomp at line 9. All words in the dictionary are downcase and so you can type in any case and get the same answer. Thanks!

    Alejandro Sierra

    May 17, 2009 at 9:43 am

  2. […] I came across this page, Solving anagrams in Ruby. […]

  3. This is a really neat idea! I may use something similar for an iphone app I’m working on…



    February 14, 2011 at 10:54 pm

  4. if (ARGV[0].upcase.split(“”).uniq.sort.join() == ARGV[1].upcase.split(“”).uniq.sort.join())
    puts “\n Yes! #{ARGV[0]} and #{ARGV[1]} are anagrams.”
    puts “\n No. they’re not anagrams.”


    August 25, 2014 at 2:17 am

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

%d bloggers like this: