Hacker News Reader

Comment by jules | Hacker News Reader

What do you mean by anagram solver? Find anagrams for a given word? Isn't that trivial by indexing words by the sorted version of the word? E.g. {"aep" -> ["ape", "pea"], ...}

View on HN

I'm trying to built a better multi-word anagram solver. If you input a 32 character string, you'll end up with hundreds of thousands of potential anagrams and most of them are pretty useless. For example, "Florence Nightingale" returns 52k results on:

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.

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.

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:

http://anagramlogic.com/

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?

I wrote this snippet ~10 years ago when learning Perl:

  for(<>){chop;$s{join'',sort split'',lc}.=" $_"}for(sort%s){/. /&&print"$_\n"}

Running against wordlist.txt was fun (anemic cinema, bedroom boredom, etc.)

Yes.

Until you get to multiple-word anagrammatic phrases, when it becomes a search problem.

(You could index a list of phrases the same way, but users wouldn't be able to type in their name and find out what phrases it jumbles into.)

Reply on news.ycombinator.com