jaw@ames-lm.UUCP (James A. Woods) (02/17/84)
# Sixty minutes of thinking of any kind is
bound to lead to confusion & unhappiness.
-- James Thurber
Bet the Subject: caught your eye. But it may as well be (in anagram
speak):
romantic pang among us
mangos moan capturing
gaunt moron campaigns
and other dubious headlines. I only know this because I possess (as far as
I know) the world's champion anagram program. Really--C code, but proprietary!
If you want to know more about the methods to such madness, send for my
paper, an abstract of which is reproduced below (the writing [about nine
"vtroff" pages] is considerably less dry than the abstract.)
In pursuing this obsession, I've corresponded with Knuth
(donald ervin knuth == hunt drink and love), who agrees with me that
it's an NP-complete problem, and D. Hofstadter, whose approach is completely
opposite of mine. Incidently, the "loonderk" causing Mr. Perlow (ihuxq!ken)
to scratch his head was referred to in SIGART Newsletter of October 1983.
This is taken from "(Janet) Kolodner", the name of a cognitive modelling
panelist speaking at the 1983 Intl. Machine Learning Workshop from the same
podium as Hofstadter.
A brief consultation with my machine-aided "steam anagramatist"
yields "elk donor", "Keno lord", "lend rook", "look nerd", "drool ken",
and "OK, Dr. Leon".
Your Humble Lexicographer,
James A. Woods
{hao | menlo70}!ames-lm!jaw
-------------------------
"ON COMPUTING ANAGRAMS (or, Recipes for Minceword Pie)"
Abstract
The combinatorial task of generating multiword anagrams is tackled.
It is presented as a variant of an NP-complete integer knapsack problem
arising from operations research; our original motivation stems from a natural
enquiry in recreational linguistics.
We outline a basic recursive solution method, and then discuss
various refinements, including: permutation suppression, the use
of a length-segmented list data structure, fast set membership testing
of canonical strings, precomputation of cases with small cardinality
(a technique lifted from the pages of dynamic programming), and other
computer code optimizations. Several language domain-specific speedups
are incorporated within the program extract.
Finally, we report on a brief investigation into the search
for minimal English pangrams, otherwise known as "holoalphabetic"
sentences.