It's a fun project! I built one several years ago, after playing around with a bunch of different approaches. I wound up with a human-guided tool that seems to work pretty well for coming up with interesting ones:
Ah, interesting! This problem is NP-complete even in if you don't specifically want anagrams that are interesting to a human.
Suppose that you only have a single letter alphabet (say "a"). Now the input string can only contain a's, so it can be represented by a number n. The dictionary also consists only of words of a's, so the dictionary can be represented as a set of numbers D a subset of the natural numbers. Now the problem of finding an anagram is finding a subset of A of D such that sum(A) = n. But this is the subset sum problem, which is NP-complete!
How are you determining the interestingness of an anagram?
Re:ITA Software's Hiring Puzzles
by tedunangst on Thursday April 22, 2010 @11:09AM
(#1285277)
Use random partitioning? If you have more than 10 letters, randomly split into roughly equal parts. Then do that 1000 times to the input string.
http://wordsmith.org/anagram/anagram.cgi?anagram=Florence+Ni...
And most of them are pretty lame e.g. "A Fleecer Tingling Hon", "A Fleecer Longing Hint" etc. It'll take hours before you come across "Flit on, cheering angel" - I want to make this process faster/easier.