3 ms·

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

by jules 17y ago

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"], ...}

asimjalis 17y ago
Yes.
- jjs 17y ago
  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.)
chime 17y ago
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+Nightingale&t=100&a=n 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.
- tedunangst 17y ago
  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.
- pwk 17y ago
  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/ http://anagramlogic.com/
- jules 17y ago
  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?
rimantas 17y ago
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.)

by jules 17y ago

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"], ...}

asimjalis 17y ago

Yes.

jjs 17y ago
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.)

chime 17y ago

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+Nightingale&t=100&a=n 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.

tedunangst 17y ago
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.
pwk 17y ago
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/ http://anagramlogic.com/
jules 17y ago
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?

rimantas 17y ago

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.)