|Perl: the Markov chain saw|
Solving Anagramsby Cody Pendant (Prior)
|on Jan 24, 2005 at 01:34 UTC||Need Help??|
Cody Pendant has asked for the
wisdom of the Perl Monks concerning the following question:
I've asked about this before but I'll be the first to admit I'm stuck on the recursion/logic of it.
By the way, there is, as far as I know, no openly-source or free anagram engine anywhere. There are some good websites (http://www.wordsmith.org/anagram/) , but no offline Perl solution that I can find.
So, assuming that I have already created a dictionary-hash of "ur-words" where
then, what's my next move? Because for single words (in the answer), it's a no-brainer. Sort letters, lookup either fails or it doesn't, here are your words.
But for multiple words in the answer? (that website gives nearly 1300 possible anagrams for "perl wisdom") I need to use a permutation algorithm on my input string, then index through each permutation, looking for a string which matches a word in my dictionary ... then look at the left-over letters and perform the same process, then the left-overs of that process..? This is where it all gets a bit misty for me.
Any help gratefully received. Which permutation module/algorithm should I use for a start? For long strings the amount of permutations is huge.