Ruby anagram solver

Question

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?

score 35 · Accepted Answer · answered Aug 23 '11 at 21:20

35

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.

answered Aug 23 '11 at 21:20

Rob Neuhaus

9,190
3
28
37

1

Great idea. How about multi word anagram solver? Like `rrenaud` => `Ad Rerun`? – Kimmo Lehto Aug 24 '11 at 06:57
@KimmoLehto split the sentences into arrays and then remove all instances of space character from the arrays. After that, sort the arrays and then match them. – Ashishkumar Pandey Apr 23 '17 at 17:51
@AshishPandey It's not totally clear what you mean. When you say "split the sentences" there is no dictionary of all possible sentences. If you mean split the input sentence and you mean to split at the spaces then you're just finding anagrams for the input words without swapping letters between words. That won't produce a result very often. – Adamantish Sep 11 '19 at 09:55
@Adamantish There will be a dictionary, the question says that there's a list of words. That's the dictionary. So, let's suppose the user inputs `teehs`, the split and a sorted array of this input would be `[ 'e', 'e', 'h', 's', 't' ]`. the program would also have another multi-dimensional hash where the keys would be the words in the dictionary and the values would be their split and sorted arrays. We can then simply loop over the values of the hash and get the matching key. Hope that makes sense. – Ashishkumar Pandey Sep 12 '19 at 11:40
@AshishPandey If you try it you'll run into problems there. Firstly, yes the sorted arrays are ok but they need to be the keys because for each one of those there may be multiple words. And that's how you'd get O(1) performance for directly looked up words. But this is only helpful for getting a single word anagram. You need to find all the words *containing* your input letters - not the exact match a hash gives - (the trie data structure in https://stackoverflow.com/a/1924561/2772719 is about the best for this) then you must recurse the search with the remaining letters. – Adamantish Sep 12 '19 at 15:18
@Adamantish of course, this was a 1-minute recommendation, not an answer. Your referred answer makes a lot of sense though implementing it in the first attempt would be challenging and hence my recommendation. – Ashishkumar Pandey Sep 12 '19 at 17:08

David Grayson · Answer 2 · 2014-02-06T16:54:29.747

11

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: https://github.com/DavidEGrayson/anagram/blob/master/david.rb

edited Feb 06 '14 at 16:54

answered Aug 23 '11 at 21:46

David Grayson

84,103
24
152
189

3

That's identical to `words.group_by {|word| word.chars.sort }` – Jörg W Mittag Aug 24 '11 at 01:10
Cool, but actually you would need to do this: `@words_hash = words.group_by {|word| word.chars.sort}; @words_hash.default = []` – David Grayson Aug 26 '11 at 14:30

score 5 · Answer 3 · answered Mar 07 '12 at 20:37

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

score 4 · Answer 4 · answered Aug 23 '11 at 21:28

4

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

answered Aug 23 '11 at 21:28

Rontologist

3,568
1
20
23

oh my, just love it! – thelastinuit Aug 30 '17 at 00:07

score 1 · Answer 5 · answered Dec 09 '13 at 17:11

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

score 1 · Answer 6 · edited May 23 '17 at 11:45

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

edited May 23 '17 at 11:45

Community

1
1

answered Aug 23 '11 at 21:20

Dan W

5,718
4
33
44

score 0 · Answer 7 · answered Jun 05 '12 at 12:44

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

Ruby anagram solver

7 Answers7