From: batkins57@...
Date: 2005-12-08T18:03:23+09:00
Subject: Re: is this a good way to find anagrams?

I went ahead and implemented my own suggestions, and just to give you
an idea of how fast you can get this, my version can find all valid
anagrams of a five-letter word ("truck") given a 274,000 word
dictionary in 0.231 seconds....real-time.

:D

batkins57@gmail.com wrote:
> One thing you could try is inverting your algorithm.  My dict/words
> file has 234,000+ entries in it.  Since you're looping through the dict
> file and then calling rodolfo on each iteration, you have to pay the
> cost of calling rodolfo 234,000 times, even though in general only a
> couple of entries in the words file are relevant.
>
> So what you could do is first find all the possible permuations of the
> letters in your given word.  Then loop through the word file once.  If
> a word matches one of the permutations in your list, remove it from the
> list of words to be checked and push it onto a separate list.  This
> should be significantly faster, since you calculate the combinations up
> front, and then do one scan through the list.
>
> You could also call out to a program like aspell or ispell to check
> your words for you.  Those programs will do something at least as fast
> as a binary search, which will take much, much  less time than scanning
> through the whole thing  - even in the worst case, a 234,000 entry file
> will be checked in 18 string comparisons, instead of 234,000.
>
> hth,
> Bill
>
> travis laduke 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.
> >
> >
> > ##these are here from when i was first testing
> > secret_word = "spine"
> > rack = "spine"
> >
> > secret_word = secret_word.split(//)
> > rack = rack.split(//)
> > test_rack = rack.to_s
> >
> > ##are there enough of the right letters in the rack to spell the word
> > from the dictionary?
> > ##i think i'm going to use funny spanish names for my methods instead
> > of descriptive names.
> > def rodolfo(secret_word, rack)
> > secret_word.each do |x|
> >      rack = rack.to_s
> >      if rack.include? x
> >          rack = rack.sub(x, '')
> >          ##p rack, x
> >      else
> >          ##puts x, ' rack don\'t work'
> >          break
> >      end
> > end
> > end
> >
> >
> > puts "reading dictionary"
> > dict = IO.readlines('/usr/share/dict/words')
> >
> > while rack
> >      puts "enter rack"
> >      rack = gets.chomp.split(//)
> >
> >      dict.each do |secret_word|
> >
> >          if rodolfo(secret_word.chomp.split(//), rack)
> >              puts secret_word.to_s
> >          end
> >      end
> > end