[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Re: is this a good way to find anagrams?

travis laduke

12/10/2005 6:14:00 AM

i goofed up my thread by using the word "anagram" incorrectly, or too loosely...
i also wanted to find all the smaller words that i can make with the letters that i have.
for example i would like for "monkey" to return with "monk" and "key" and "money" and so on, not just 6 letter
words.

i think this makes it so you can't use the methods where you sort everything first, which i discovered didnt work
all the time if you want smaller words too.
if you sort "monkey" you get "ekmnoy" but if you sort "monkeys" you get "ekmnosy", which means if your letters
are "monkeys", you wont get "monkey" back. that s is a big monkey wrench between o and y.

maybe i should do the sort first way on the words in the dictionary that have the same amount of letters, and
then do some other way on all the words that have less letters, and skip all the words that are too long?

i'm still glad for all the nice anagram (in the strict sense) finder code in this thread. this is the best list ever.

----- Original Message -----
From: Brian Schröder <ruby.brian@gmail.com>
Date: Friday, December 9, 2005 4:15 am
Subject: Re: is this a good way to find anagrams?

> On 09/12/05, Brian Schröder <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-sch...
>
> Stringed instrument chords: http://chordlist.brian-sch...
>


1 Answer

Martin DeMello

12/12/2005 7:58:00 AM

0

wrong@socal.rr.com wrote:
> i goofed up my thread by using the word "anagram" incorrectly, or too
> loosely... i also wanted to find all the smaller words that i can
> make with the letters that i have. for example i would like for
> "monkey" to return with "monk" and "key" and "money" and so on, not
> just 6 letter words.

One interesting way to do subset finding in words is to hook up a fast
bignum library (I think ruby/gsl should do this), and index each letter
with a prime number, so that a word maps to the product of its letters.
Then word_b contains word_a if number_b % number_a == 0.

martin