From: Dave Thomas <dave@...>
Date: 2008-12-28T03:46:26+09:00
Subject: Re: Buiding anamgrams


On Dec 27, 2008, at 2:59 AM, andrea wrote:

> Thanks a lot everyone, now I already posted but don't know why it
> doesn't appear my message.
> Anyway you're right Axel, this is the first "solution" to the problem
> but it's really too slow for any reasonable large size of the string.
>
> This is the code, any hint about style or whatever is welcome:
> http://pastie.textmate.org/private/rp4ivw36vefuz07twjlw3g

I think a faster approach, particularly to find multiple anagrams, is  
to create a signature or hash with the property that each word in a  
set of anagrams will have the same hash code. Finding anagrams then  
becomes a problem of building lists of words with the hash hash code.

A convenient hash is simply to take all the letters in each work and  
sort them, so that "dog" becomes "dgo" and "god" also becomes "dgo".  
Because they have the same hash, they are anagrams.

Here's the code from the PickAxe[1] that uses this to find anagrams:

   http://pastie.textmate.org/private/yttznlgzcf9czdkc7vxea

and here are some simple tests:

   http://pastie.textmate.org/private/stv3sxaecc6z8uwxclldba

In fact, I use this as an example of Gem packaging, so you can  
actually do

    gem install anagram

and get the whole thing.


Cheers


Dave

[1] http://pragprog.com/titles/ruby3