From: Axel Etzold <AEtzold@...>
Date: 2008-12-27T09:27:08+09:00
Subject: Re: Buiding anamgrams

Dear Andrea,

> I want to create an efficient module to generate every possible
> anagrams of a word, of any given size...
> I already done this in python, I want to see how can it be elegant in
> ruby...
> I need a good permutation algorithm (this
> http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml
> works fine) and I'd like to use enumerators in the best and most
> efficient way.
> 
> I also looked at callcc which is great for backtracking, could be used
> in this case??


Permutations become quite unwieldy very quickly ... maybe you'd have a look
at Hidden Markov Models instead. There are several algorithms associated
to these models. I think what you'd want to do is to apply the "forward algorithm"
to estimate how probable a given word is, given the probability of letter x2 succeeding
letter x1 in the language you are trying to form anagrams in ( ... download some novels
from project Gutenberg, split them into pairs of letters and count.....) .

For the forward algorithm, look at the concrete example here:

http://en.wikipedia.org/wiki/Viterbi_algorithm

There once was a Ruby quiz about Markov chains to help you with Ruby:

http://www.rubyquiz.com/quiz74.html

To test whether a given word exists in language X, you could use raspell in conjunction with
aspell:

http://blog.evanweaver.com/files/doc/fauna/raspell/files/README.html

Best regards,

Axel 
-- 
Psssst! Schon vom neuen GMX MultiMessenger geh�rt? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger