On 09/12/05, Brian Schröäer <ruby.brian / gmail.com> wrote:
> On 08/12/05, travis laduke <wrong / socal.rr.com> wrote:
> > it seems to me, with computers these days, this should finish
> > instantly, not take like 20 seconds.
> > also, please help me make my ruby more ruby-like. i'm new to ruby,
> > not that i know any other language.
> >
> > [snip]
>
> if you want to find lots of anagrams against the same database it
> would make sense to create an index. Make a hash that is indexed by
> the sorted letters and let it point to a list of words that yield this
> letter. After you have done this once, you can lookup anagrams in O(1)
>
> cheers,
>
> Brian
>

Here comes a short implementation:

hash =
    File.read('/usr/share/dict/words').
    downcase.
    split(/\n/).
    inject(Hash.new { | h, k | h[k] = [] }) { | h, w |
h[w.split(//).sort] << w; h }


ARGV.each do | word |
  puts "Anagrams for #{word}: #{hash[word.split(//).sort].join(' ')}"
end

>>>>>
Anagrams for ruby: ruby bury ruby
Anagrams for duck: duck
Anagrams for type: type
Anagrams for truck: truck
Anagrams for brian: brain brian rabin brain
Anagrams for sort: rots sort tors
Anagrams for index: index nixed

Here are the timings:

The calculation of the index took 3.34749s

Lookup of 7 words took 0.000195s

And lookup of the words scales linearly, so for certain applications
(building an anagram-server e.g.) this may be the best possibility.

Cheers,

Brian

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/