From: Brian Adkins <lojicdotcom@...>
Date: 2007-10-20T07:20:03+09:00
Subject: Re: combinations listing

On Oct 19, 3:38 pm, Michael Linfield <globyy3...@hotmail.com> wrote:
> Brian Adkins wrote:
> >> Feel free to improve it if you see a flaw or a better way of doing it
>
> > Can your program solve this anagram (a very common word)?
> > "aaabcehilllpty"
>
> > It might take a while. The word provides a hint (in two separate ways)
> > for an improvement.
>
> > Using my code from another post will speed up the permutation
> > generation by a factor of 3, but that is no match for an O(n!)
> > algorithm. I think you'll need a new technique for longer words.
>
> > Also, since the anagram and the actual word must be the same length to
> > match, you can partition the dictionary by word size. That and the
> > hint above should get you a long way down the road.
>
> > Brian Adkins
>
> Alright i see your point lol, so are you suggesting that the actual
> dictionaries be split up? in a sense of...
>
> word = "foobar"
> res = word.split('')
>
> if res.size > 3
>   #use dictionary 1
> end
>
> if res.size > 6
>   #use dictionary 2
> end
>
> ect...
>
> one way or another, the only speed issue here is generating the
> permutations, searching the dictionary is pretty quick from what ive
> seen.
> The clue was alphabetically, sadly i didnt want to wait for my program
> to finish that lol. I'm kind of hazy as to what that clue might suggest,
> my interpretation is to possibly grep out all the words that are of the
> same length as the word entered.
>
> word = gets.chomp
> res = word.split('')
> size = res.length
> # so now size would equal 14 if you used the word 'alphabetically'
>
> file = open('dict1.txt') {|p|  p.readlines}
> dict = []
>  #when statement that shoves all words = to 14 into the dict array
> end

There are probably better ways to do this, but the first thing that
popped into my head was the following:

Create a hash with the key being a string containing the letters of a
dictionary word in sorted order and the value being an array of words
sharing that key.

Then simply take the anagram, sort the letters and do a hash lookup to
get all the words that share the same letters.

Alternatively, create an array of pairs with the first element being
the string of sorted letters and the second element being the word and
do a binary search with the sorted anagram.

So, the "alphabetically" clue was this sorting technique.

HTH

Brian Adkins