I am wanting to write a anagram type solver in Ruby but it will work against a list of words, like so.

List of words is:

the these one owner

I would allow the user to input some letters, e.g noe, and it would search the word list for words that it can make using the letters the user has input and would bring back one and if they entered "eth" or even "the" it would bring back the. I have been trying to think of a efficient way to do this but I have been looping around each word, match a letter in the word, checking the word for each letter and both lengths match. Can anyone give advice of a better and more efficient way to do this?

0

7 Answers

The big idea is that all anagrams are identical when sorted. So if you build a hash (don't know what Ruby calls these) of lists, where the keys are sorted words and the value is the list of words that sorts to the given key, then you can find anagrams very quickly by sorting the word and looking up in your hash.

6

rrenaud's answer is great, and here is an example of how to construct such a hash in ruby, given an array named "words" that contains all of the words in your dictionary:

@words_hash = words.each_with_object(Hash.new []) do |word, hash| hash[word.chars.sort] += [word] end

The code above assumes ruby 1.9.2. If you are using an older version then chars won't exist but you can use .split('').sort.

The default object of the hash is set to be the empty array, which makes the coding easier in some cases because you don't have to worry about the hash giving you nil.

Source:

2

One solution could be:

def combine_anagrams(words) output_array = Array.new(0) words.each do |w1| temp_array = [] words.each do |w2| if (w2.downcase.split(//).sort == w1.downcase.split(//).sort) temp_array.push(w2) end end output_array.push(temp_array) end return output_array.uniq end

I couldn't resist solving this ruby quiz :)

class String def permutation(&block) arr = split(//) arr.permutation { |i| yield i.join } end end wordlist = ["one", "two"] "noe".permutation do |i| puts "match found: #{i}" if wordlist.include?(i) end

The basic idea is that it creates and array and uses it's permutation function to come up with the result. It may not be efficient but I find it elegant. :D

1

This might be what you're looking for: Solving Anagrams In Ruby

Here's another approach (it's the top response): Anagram Solver In Python

Here's quite similar of mine. Reading from a dictionary file and comparing sorted chars as an array. Sorting is done on preselected candidates.

def anagrams(n) text = File.open('dict.txt').read candidates = [] text.each_line do |line| if (line.length - 1) == n.length candidates << line.gsub("\n",'') end end result = [] candidates.each do |word| if word.chars.sort == n.chars.sort result << word end end result end 
def combine_anagrams(words) cp = 0 hash = Hash.new [] words.each do |word| cp += 1 (cp..words.count).each do |i| hash[word.to_s.chars.sort.join] += [word] end hash[word.to_s.chars.sort.join] = hash[word.to_s.chars.sort.join].uniq end return hash end