I discovered the most effective anagram in English
I found the best anagram in English
I deliberate to publish this final week someday however then I wrote a line
of code with three errors and that
took over the weblog.
A couple of years in the past I discussed in passing that
in the 1990s I had constructed a listing of all the anagrams
in Webster’s Second Worldwide dictionary. (The
Webster’s headword list was accessible
on-line.)
This was simple to do, even on the time, when the glossary itself, at
2.5 megabytes, was a file of great dimension. Perl and its cousins
weren’t but frequent; in these days I used Awk. However the activity isn’t
very totally different in any cheap language:
# Course of glossary
whereas (my $phrase = <>) {
chomp $phrase;
my $sorted = be a part of "", type break up //, $phrase; # regular kind
push @{$anagrams{$sorted}}, $phrase;
}
for my $phrases (values %anagrams) {
print "@$wordsn" if @$phrases > 1;
}
The important thing method is to cut back every phrase to a regular kind in order that
two phrases have the identical regular kind if and provided that they’re anagrams
of each other. On this case we do that by sorting the letters into
alphabetical order, in order that each megalodon and moonglade grow to be
adeglmnoo.
Then we insert the phrases right into a (hash | associative array |
dictionary), keyed by their regular varieties, and two or extra phrases are
anagrams in the event that they fall into the identical hash bucket. (There may be some
dialogue of this system in Higher-Order
Perl pages 218–219 and elsewhere.)
(The factor you do not need to do is to compute each permutation of
the letters of every phrase, on the lookout for permutations that seem within the
glossary. That’s akin to sorting an inventory by computing each
permutation of the record and on the lookout for the one that’s sorted. I
would not have talked about this, however somebody on StackExchange truly
requested this query.)
Anyway, I digress. This text is about how I used to be sad with the
outcomes of the easy process above. From the Webster’s Second
record, which accommodates about 234,000 phrases, it finds about 14,000
anagram units (some with greater than two phrases), consisting of 46,351
pairs of anagrams. The record begins with
aal ala
and ends with
zolotink zolotnik
which exemplify the issues with this straightforward method: lots of the
46,351 anagrams are apparent, uninteresting and even trivial. There
should be good ones within the record, however learn how to discover them?
I appeared within the record to seek out the longest anagrams, however they had been additionally
disappointing:
cholecystoduodenostomy duodenocholecystostomy
(Webster’s Second accommodates a considerable amount of scientific and medical
jargon. A cholecystoduodenostomy is a surgical procedure to
create a channel between the gall bladder (cholecysto-) and the
duodenum (duodeno-). A duodenocholecystostomy is similar factor.)
This instance made clear no less than one of the issues with boring
anagrams: it isn’t that they’re too quick, it is that they’re too
easy. Cholecystoduodenostomy and duodenocholecystostomy are 22
letters lengthy, however the anagrammatic relation between them is clear:
chop cholecystoduodenostomy into three components:
cholecysto duodeno stomy
and rearrange the primary two:
duodeno cholecysto stomy
and there you may have it.
This gave me the thought to attain a pair of anagrams based on how
many chunks one needed to be lower into with a view to rearrange it to make
the opposite one. On this plan, the “cholecystoduodenostomy / duodenocholecystostomy” pair would rating 3,
simply barely above the minimal potential rating of two. One thing even a
tiny bit extra attention-grabbing, say “abler / blare” would rating greater, in
this case 4. Even when this technique did not lead me on to the
most attention-grabbing anagrams, it might be an enormous step in the fitting
path, permitting me to remove the least attention-grabbing.
This rule would decide each “aal / ala” and “zolotink / zolotnik” as
being uninteresting (scores 2 and 4 respectively), which is an effective
end result. Be aware that another boring-anagram issues could be seen as
particular circumstances of this one. For instance, quick anagrams by no means have to
be lower into many components: no four-letter anagrams can rating greater
than 4. The trivial anagramming of a phrase to itself all the time scores 1,
and nontrivial anagrams all the time rating greater than this.
So what we have to do is: for every anagram pair, say
acrididae (grasshoppers)
and cidaridae (sea
urchins), discover the smallest variety of chunks into which we will chop
acrididae in order that the chunks could be rearranged into cidaridae.
One might do that with a intelligent algorithm, if one had been accessible.
There is a clever algorithm,
primarily based on discovering most unbiased units in a sure graph. (Extra
about this tomorrow.) I didn’t discover this algorithm on the time; nor
did I strive. As a substitute, I used a brute-force search. Or somewhat, I used a
very small quantity of cleverness to cut back the search house, after which
used brute-force search to look the decreased house.
Let’s take into account a instance, scoring the anagram “abscise / scabies”.
You would not have to contemplate each potential permutation of
abscise. Relatively, there are solely two potential mappings from the
letters of abscise to the letters of scabies. You understand that the
C should map to the C, the A should map to the A, and so
forth. The one query is whether or not the primary S of abscise maps to
the primary or to the second S of scabies. The primary mapping offers
us:
and the second offers us
as a result of the S and the C now not go to adjoining positions. So
the minimal variety of chunks is 5, and this anagram pair will get a rating
of 5.
To totally analyze cholecystoduodenostomy by this technique required contemplating 7680
mappings. (120 methods to map the 5 O‘s × 2 methods to map the 2
C‘s × 2 methods to map the 2 D‘s, and so on.) Within the Nineteen Nineties this took a
whereas, however not prohibitively lengthy, and it labored nicely sufficient that I
didn’t hassle to attempt to discover a higher algorithm. In 2016 it might
in all probability nonetheless run faster than implementing the utmost unbiased
set algorithm. Sadly I’ve misplaced the code that I wrote then
so I can not evaluate.
Assigning scores on this manner produced a scored anagram record which
started
2 aal ala
and ended
4 zolotink zolotnik
and someplace within the center was
3 cholecystoduodenostomy duodenocholecystostomy
all poor scores. However sorted by rating, there have been treasures on the
finish, and the clear winner was
14 cinematographer megachiropteran
I declare this the one finest anagram in English. It’s 15 letters
lengthy, and the one letters that keep collectively are the E and the R.
“Cinematographer” is as acquainted as a 15-letter phrase could be, and
“megachiropteran” means a large bat. GIANT BAT! DEATH FROM
ABOVE!!!
And there’s no severe competitors. There was one other 14-pointer,
however each its phrases are Webster’s Second jargon that no one is aware of:
14 rotundifoliate titanofluoride
There are not any rating 13 pairs, and the rating 12 pairs are all obscure.
So that is the winner, and a deserving winner it’s.
I believe there’s something within the record to make everybody completely happy. In the event you
are the kind of one who enjoys anagrams, the record rewards informal
shopping. A couple of examples:
7 admirer married
7 admires sidearm8 negativism timesaving
8 peripatetic precipitate
8 scepters respects
8 shortened threnodes
8 soapstone teaspoons9 earringed grenadier
9 excitation intoxicate
9 integrals triangles
9 ivoriness revisions
9 masculine calumnies10 coprophagist topographics
10 chuprassie haruspices
10 citronella interlocal11 clitoridean directional
11 dispensable piebaldness
“Clitoridean / directional” has been one in every of my favorites for years.
However my favourite of all, though it scores solely 6, is
6 yttrious touristy
I believe I’d adore it simply because the phrase yttrious is so
pleasant. (What a debt we owe to Ytterby,
Sweden!)
I additionally somewhat like
5 notaries senorita
which reveals that even a few of the low-scorers could be value taking a look at.
Clearly my chunk rating isn’t the top of the story, as a result of “notaries
/ senorita” ought to rating higher than “abets / baste” (which is boring)
or “Acephali / Phacelia” (no matter these are), additionally 5-pointers. The
size of the phrases needs to be value one thing, and the familiarity of
the phrases needs to be value much more.
Listed below are the outcomes:
In former occasions there was a restaurant in Philadelphia named
“Soupmaster”. My finest unassisted anagram discovery was noticing
that that is an anagram of “mousetraps”.
comparing the two algorithms I wrote for computing scores. ] [ Addendum 20170222: An earlier version of this article mentioned the
putative 11-pointer “endometritria / intermediator”. The word
“endometritria” seemed pretty strange, and I did look into it before I
published the article, but not carefully enough. When Philip Cohen
wrote to me to question it, I investigated more carefully, and
discovered that it had been an error in an early
WordNet release, corrected (to
“endometria”) in version 1.6. I didn’t remember that I had used
WordNet’s word lists, but I am not surprised to discover that I did. ] [ Addendum 20170223: More about this ] [ Addendum 20170507: Slides from my !!Con 2017 talk are now available. ] [ Addendum 20170511: A large amount of miscellaneous related material ]