This is a fun read, I've always enjoyed anagrams and palindromes. The "best anagram" was cinematographer megachiropteran.
However, it comes across as a little "smarter than thou" with the section:
"The thing you do not want to do is to compute every permutation of the letters of each word, looking for permutations that appear in the word list. That is akin to sorting a list by computing every permutation of the list and looking for the one that is sorted. I wouldn't have mentioned this, but someone on StackExchange actually asked this question."
That statement makes sense to me when I think about it, but it wouldn't have appeared as totally obvious to me from the outset. And I can't see casting derision at someone because they asked this question.
It's probably obvious enough once you've buried your head in this train of thought continuously for weeks. Thank god we don't have to do that because this helpful person has just told us.
I think that paragraph perfectly demonstrates why all the commenters on Why I Don’t Talk to Google Recruiters (https://news.ycombinator.com/item?id=13696004) who insist that programmers don't need to know algorithms are wrong. It should be immediately obvious to anyone with a cursory understanding of algorithms that computing all the permutations of every word is much more expensive than necessary, and from there it's not all that hard to figure out that sorting the letters produces the desired effect.
The observation that two words are anagrams if they contain all the same letters isn't a huge leap from two words that contain all the same letters are anagrams.
That being said: Sorting isn't required. (An O(kn) solution exists to beat your O(nk log k))
Yeah, there are other solutions, such as allocating an array of 26 letters (ignoring accents) and using that to count, but sorting is easy and is generally fast enough.
It's not entirely clear that the O(nk) solution actually wins because k is small in this case, and so log(k) is very small. Unless you do some careful bit packing, the O(nk) algorithm will use more memory, which could make it slower because of increased cache misses.
The O(nk) solution has fewer branches (O(1) versus O(log k)), and even if you use a naïve implementation, O(nk) will still fit into L1 (assuming n is bigger than k).
Not even close. The lexicon is 230k words, times 26 letters is nearly 6MB. The i7 has a 64kB L1 cache and a 246kB L2 cache.
I think the only way to resolve this would be to actually do the experiment. I wouldn't bet my life savings on the outcome either way, but I'll give you even odds at low stakes that sorting is faster.
Is it though? There's only 230k words in that list, and most words aren't that long. Building a trie and then trying all the permutations of all of the words seems like it would finish in a reasonable amount of time. Even then O(n^2) approach of comparing pairwise would probably get you to a reasonable time. Especially since this is a one-time thing and doesn't get run over and over.
And your argument is kind of silly when in the very same article when he uses brute force to see how many segments. Shouldn't he have found the most optimal algorithm for that instead of brute forcing it?
Sorting the words is significantly easier in virtually every programming language than testing all of the permutations. So the "it should finish in a reasonable amount of time" isn't a good excuse, since you're doing more work than necessary in order to implement the suboptimal solution.
If it's not obvious, it's probably because you've slightly misunderstood the problem somewhere. You have a finite list of items, and you want to create matches between them based on how many of each letter they have. Now it's simple, right?
First time I found about this same approach to discover anagrams was in John Bentley's Programming Pearls, 1st Edition (which I believe came out in 1986, and was in itself a collection of columns from previous years).
That's a lot of fun. I'd like to see someone go further with some of the suggestions the author mentions at the end, like weighting the scores by word familiarity and word length.
I did something like that for multiword anagrams: scoring them by their probability in a word-bigram model of English. It's expensive because I had it pick the best permutation of the words, by brute force. It's far from a measure that could really judge "this is a great anagram", but there are so astronomically many boring ones to filter out that it's still a big help.
I gave that a shot using Wordnet. It's flawed for a few reasons. A lot of the more unusual words in his list aren't in Wordnet. I also had the stem the words first, and had to pick just the most used sense if the word had multiple senses.
So, the list is only those pairs that made it through the processing.
Kind of related: The anagrams problem is probably my favourite interview question to dole out. Always shows completely different ways of thinking and normalising things.
The list of examples in the 7-11 range seemed to have a high number of pairs that have strangely coincidental meanings somehow. I thought maybe that was because they are hand-picked, but looking at the complete list, I honestly see more of those than I'd expect. I'm not sure why it's surprising, there's no actual pattern in a pair, and it's not surprising that lots of pairs of words have some way to connect them. But it still feels surprising when looking at them. It's like a lot of high scoring pairs of words share some kind of root, even though high scoring should mean high dissimilarity.
Anyway, great post. Weekend coding projects looking for anagrams and palindromes and boggle solutions are often rewarding for me, above and beyond just being fun.
I bet that the "strangely coincidental meanings" are your human brain doing pattern-matching, rather than any etymological similarities. Which I think is why the anagrams are so fun in the first place!
Totally, I think you're right. I suspect there are lots of infrequent and different ways to associate two words, and my brain conflates them all into one concept. It would be surprising if a random dissimilar anagram was frequently a pair of synonyms, but it might not be surprising that a pair has some association of some kind, where there are tens or hundreds of different ways to associate words.
Probably not a perfect analogy, but this is vaguely reminding me of Ramsey's theorem from combinatorics; the idea that if you have enough stuff, some of it must be structured.
Words with similar letter distributions will tend to be from the same root languages, which frequently maps to category of discourse (scientific, sophisticated, coarse, exotic, etc.)
So the author ends up scoring anagrams by the minimal number of 'chunks' such that one word can be rearranged into the other, and points out that this maps to the NP-complete independent set problem.
Another way you can do it is to score each pair by the length of the longest shared substring, which can be done in linear time with a suffix trie or quadratic with dynamic programming. Under that metric the 15-length word is no longer 'best', you'd end up picking the longest pair that fully permutes the other word.
Sadly, it turns out our genius idea doesn't work so well - the infamous cholecystoduodenostomy/duodenocholecystostomy is in joint fourth place, and the scarcely any better duodenopancreatectomy/pancreatoduodenectomy is joint second.
mjd's key insight was that good anagrams are ones where all the letters are thoroughly scrambled; both of the cases above are ones where large blocks of letters remain intact. I don't know if you've had scrambled eggs where large lumps of white or yolk remain intact, but i have, and they're vile.
So, anyway, perhaps a better edit distance metric is one which allows cut-and-paste of whole blocks as an edit, since it would give those words much lower scores. My years of DNA-hunching immediately led me to think of sequence alignment algorithms, because that kind of cut-and-paste is exactly what happens in DNA:
But i'm not sure those algorithms are much good, because they model the editing as deleting, inserting, and modifying runs of letters, rather than moving them around.
Next, i thought of compression, because that often works by finding repeated runs of characters, and also i don't really know any other areas of string algorithms. What if you concatenated two strings, compressed them using LZ77, and measured the amount of compression? Or what if you did it with something simpler and more local, like Predictor [1]? Could you use the Burrows–Wheeler transform?
I had the best luck with "Anagrams by percent of string not part of longest common substring, then length"
The top-to-bottom ranking isn't quite right...need some better way to push down short words, but it does seem to put most of the good stuff near the top.
The article gives an example, but to make it a bit more explicit: Levenshtein distance is a poor measure for the intuitive notion of how "non-trivial" an anagram is. Moving a chunk of letters together results in a high edit distance, but low complexity.
If you rank the entire list of anagrams by edit distance, the highest pair is "anatomicophysiologic" and "physiologicoanatomic", with an edit distance of 16 but a chunk score of only 3.
The Levenshtein distance from duodenocholecystostomy to cholecystoduodenostomy is actually pretty high: 14. Transposing two contiguous chunks of letters has a high edit distance if both chunks are long.
A "good" anagram doesn't just have letters being moved a long distance, but also requires that the movements of letters be independent, something that Levenshtein distance doesn't measure.
Because his distance measure is anagram specific
and thus more appropriate than a general one.
(Technically speaking, a proper distance measure requires a distance of 0 for equal strings, so perhaps he should pick the number of splitting points rather than the number of resulting fragments.)
It's good fun to go find anagrams of friends and family. One of my nephew's comes out Alpaca Tits. He's not real happy about it but the rest of us think it's pretty good.
"nonuniversalist" and "involuntariness", listed in another comment, both have a theological aspect. While not terribly common, they're not hard to understand either.
Love this guy's blog. His article about Your Age as a Fraction [0] caught my eye a couple years ago and I've been hooked ever since. I love checking the script to see how far into my year I am.
Basically, if you run "watch ./remaining.py" on your command line, you can see a running countdown of how long is left in the day, month, year, and your life.
Thanks! This is my site :) At some point I'll take the time to make it more beginner-friendly and have a better landing page/etc. Any suggestions welcome :)
Fun stuff - especially debugging the time printout ;)
A really ancient but still functioning site I always go to is wordsmith.org. He calls it "Internet anagram server" == "I rearrangement servant" !
"Timesaving negativism" said the
earringed grenadier,
with dispensable piebaldness,
"can be the intermediator for chronic endometritria!"
"Ah nay!" the cinematographer megachiropteran replied!
"it is only with maths--integrals, triangles,
that can cause such excitation, can intoxicate!"
But I, though their admirer, now married
had to disagree: "it would be a series of masculine calumnies
to give such clitoridean, directional advice to women!
We cannot precipitate such peripatetic thoughts!"
In case anyone is wondering, the two lines above are anagrams of each other. It's pretty impressive, any hints on the method you use to come up with this?
Work on both sides at once. I knew the phrase had to contain the word "anagram", so I started with that. At first, it was "better anagram", and so it looked like this:
better anagram lerrneet
letter rearrangement ba
So then I think of a word that both uses up the excess letters and can reasonably fit into the phrase. Whatever letters in the word that are not in the stock for that side get added to the other side. Sometimes I add words specifically to up vowel count or supply low frequency letters needed for words that fit that half of the phrase.
At some point, I had an excess 's', so "better" got turned into "best", and I had to use up its excess "ter", which got stuck with an excess 'u' to make "true". I also had an excess 'n', so a "the" became "then". Those somewhat awkward words go in last, which is where that "True then, as" came from. Getting rid of the last letters on both sides is the hardest part, because there is rarely a perfect word that uses up all your letters, just like in Scrabble. Sometimes you just have to unravel a few words and try different ones in their place. In the end, I just ran out of time to work on it.
It's a bonus if I can get near synonyms on both sides, like "transcend" and "goes beyond"
Of course, the key idea of the linked article is that it's easy to find long anagrams, but it's hard to find interesting ones. The anagram "megachiropteran = cinematographer" is ranked higher than "conversationalists = conservationalists" because of the more complex rearrangement.
112 comments
[ 3.1 ms ] story [ 353 ms ] threadHowever, it comes across as a little "smarter than thou" with the section:
"The thing you do not want to do is to compute every permutation of the letters of each word, looking for permutations that appear in the word list. That is akin to sorting a list by computing every permutation of the list and looking for the one that is sorted. I wouldn't have mentioned this, but someone on StackExchange actually asked this question."
That statement makes sense to me when I think about it, but it wouldn't have appeared as totally obvious to me from the outset. And I can't see casting derision at someone because they asked this question.
That being said: Sorting isn't required. (An O(kn) solution exists to beat your O(nk log k))
Not even close. The lexicon is 230k words, times 26 letters is nearly 6MB. The i7 has a 64kB L1 cache and a 246kB L2 cache.
I think the only way to resolve this would be to actually do the experiment. I wouldn't bet my life savings on the outcome either way, but I'll give you even odds at low stakes that sorting is faster.
And your argument is kind of silly when in the very same article when he uses brute force to see how many segments. Shouldn't he have found the most optimal algorithm for that instead of brute forcing it?
Nice solution to put the (sorted by letters) words into a hash table to find the anagrams.
So, the list is only those pairs that made it through the processing.
https://gist.github.com/anonymous/e69f448fa08481603d1ca77ea7...
Would have been better if I had also weighted using his approach, as pairs like "theater theatre" end up on top.
Still interesting though. It found these, which I liked:
It's flawed too, but does put some good ones at the top.
https://gist.github.com/anonymous/ec28b75fb6c841b56def8eefec...
The list of examples in the 7-11 range seemed to have a high number of pairs that have strangely coincidental meanings somehow. I thought maybe that was because they are hand-picked, but looking at the complete list, I honestly see more of those than I'd expect. I'm not sure why it's surprising, there's no actual pattern in a pair, and it's not surprising that lots of pairs of words have some way to connect them. But it still feels surprising when looking at them. It's like a lot of high scoring pairs of words share some kind of root, even though high scoring should mean high dissimilarity.
Anyway, great post. Weekend coding projects looking for anagrams and palindromes and boggle solutions are often rewarding for me, above and beyond just being fun.
Probably not a perfect analogy, but this is vaguely reminding me of Ramsey's theorem from combinatorics; the idea that if you have enough stuff, some of it must be structured.
Another way you can do it is to score each pair by the length of the longest shared substring, which can be done in linear time with a suffix trie or quadratic with dynamic programming. Under that metric the 15-length word is no longer 'best', you'd end up picking the longest pair that fully permutes the other word.
https://en.wikipedia.org/wiki/Levenshtein_distance
But then i realised that it was only obvious to me because i spent years hunched over a computer crunching DNA sequences.
I'd also be interested in normalising edit distance by length somehow. It's no coincidence that higher-scoring words tend to be longer.
https://gist.github.com/anonymous/431b163b2a2d532bfd0a3bdcc7...
I sorted it reverse so that the interesting pairs would be on top.
Compare to his original scored list, here: http://pic.blog.plover.com/lang/anagram-scoring/anagrams-sco...
Sadly, it turns out our genius idea doesn't work so well - the infamous cholecystoduodenostomy/duodenocholecystostomy is in joint fourth place, and the scarcely any better duodenopancreatectomy/pancreatoduodenectomy is joint second.
mjd's key insight was that good anagrams are ones where all the letters are thoroughly scrambled; both of the cases above are ones where large blocks of letters remain intact. I don't know if you've had scrambled eggs where large lumps of white or yolk remain intact, but i have, and they're vile.
So, anyway, perhaps a better edit distance metric is one which allows cut-and-paste of whole blocks as an edit, since it would give those words much lower scores. My years of DNA-hunching immediately led me to think of sequence alignment algorithms, because that kind of cut-and-paste is exactly what happens in DNA:
https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...
https://en.wikipedia.org/wiki/BLAST
But i'm not sure those algorithms are much good, because they model the editing as deleting, inserting, and modifying runs of letters, rather than moving them around.
Next, i thought of compression, because that often works by finding repeated runs of characters, and also i don't really know any other areas of string algorithms. What if you concatenated two strings, compressed them using LZ77, and measured the amount of compression? Or what if you did it with something simpler and more local, like Predictor [1]? Could you use the Burrows–Wheeler transform?
[1] https://tools.ietf.org/html/rfc1978 - your daily obscure blast from the past!
The top-to-bottom ranking isn't quite right...need some better way to push down short words, but it does seem to put most of the good stuff near the top.
https://gist.github.com/anonymous/ec28b75fb6c841b56def8eefec...
If you rank the entire list of anagrams by edit distance, the highest pair is "anatomicophysiologic" and "physiologicoanatomic", with an edit distance of 16 but a chunk score of only 3.
A "good" anagram doesn't just have letters being moved a long distance, but also requires that the movements of letters be independent, something that Levenshtein distance doesn't measure.
(Technically speaking, a proper distance measure requires a distance of 0 for equal strings, so perhaps he should pick the number of splitting points rather than the number of resulting fragments.)
Rex Tillerson -> Risen Ex Troll
is pretty amazing. Not sure how it would score with the OP's metric though - typing this as I'm on the ski lift lol
(courtesy of Lisa Simpson)
Clint Eastwood = Old West Action
Madam Curie = Radium came
It's good fun to go find anagrams of friends and family. One of my nephew's comes out Alpaca Tits. He's not real happy about it but the rest of us think it's pretty good.
not original , but certainly on topic.
[0]: http://blog.plover.com/math/age-fraction-2.html
https://gist.github.com/jedberg/61b2587b298af92adc5f985b11a2...
Basically, if you run "watch ./remaining.py" on your command line, you can see a running countdown of how long is left in the day, month, year, and your life.
Probably not the best approach, but it did unearth some interesting pairs.
Plus one that is marked easy: MYTH. Maybe I'm just an idiot, but I cannot think of an anagram for MYTH.
[0] http://wordlist.aspell.net/
it's extremely fun, though it's scrabble-focused, so you'll see a lot of weird words that you are expected just to have memorised.
"Timesaving negativism" said the earringed grenadier, with dispensable piebaldness, "can be the intermediator for chronic endometritria!"
"Ah nay!" the cinematographer megachiropteran replied! "it is only with maths--integrals, triangles, that can cause such excitation, can intoxicate!"
But I, though their admirer, now married had to disagree: "it would be a series of masculine calumnies to give such clitoridean, directional advice to women! We cannot precipitate such peripatetic thoughts!"
a letter rearrangement goes beyond the plain, ordinary substitutions of vain academic men.
At some point, I had an excess 's', so "better" got turned into "best", and I had to use up its excess "ter", which got stuck with an excess 'u' to make "true". I also had an excess 'n', so a "the" became "then". Those somewhat awkward words go in last, which is where that "True then, as" came from. Getting rid of the last letters on both sides is the hardest part, because there is rarely a perfect word that uses up all your letters, just like in Scrabble. Sometimes you just have to unravel a few words and try different ones in their place. In the end, I just ran out of time to work on it.
It's a bonus if I can get near synonyms on both sides, like "transcend" and "goes beyond"
18 letters
17 letters 16 letters 15 letters