File: gawk.info,  Node: Anagram Program,  Next: Signature Program,  Prev: Igawk Program,  Up: Miscellaneous Programs

11.3.10 Finding Anagrams from a Dictionary
------------------------------------------

An interesting programming challenge is to search for "anagrams" in a
word list (such as '/usr/share/dict/words' on many GNU/Linux systems).
One word is an anagram of another if both words contain the same letters
(e.g., "babbling" and "blabbing").

   Column 2, Problem C, of Jon Bentley's 'Programming Pearls', Second
Edition, presents an elegant algorithm.  The idea is to give words that
are anagrams a common signature, sort all the words together by their
signatures, and then print them.  Dr. Bentley observes that taking the
letters in each word and sorting them produces those common signatures.

   The following program uses arrays of arrays to bring together words
with the same signature and array sorting to print the words in sorted
order:

     # anagram.awk --- An implementation of the anagram-finding algorithm
     #                 from Jon Bentley's "Programming Pearls," 2nd edition.
     #                 Addison Wesley, 2000, ISBN 0-201-65788-0.
     #                 Column 2, Problem C, section 2.8, pp 18-20.

     /'s$/   { next }        # Skip possessives

   The program starts with a header, and then a rule to skip possessives
in the dictionary file.  The next rule builds up the data structure.
The first dimension of the array is indexed by the signature; the second
dimension is the word itself:

     {
         key = word2key($1)  # Build signature
         data[key][$1] = $1  # Store word with signature
     }

   The 'word2key()' function creates the signature.  It splits the word
apart into individual letters, sorts the letters, and then joins them
back together:

     # word2key --- split word apart into letters, sort, and join back together

     function word2key(word,     a, i, n, result)
     {
         n = split(word, a, "")
         asort(a)

         for (i = 1; i <= n; i++)
             result = result a[i]

         return result
     }

   Finally, the 'END' rule traverses the array and prints out the
anagram lists.  It sends the output to the system 'sort' command because
otherwise the anagrams would appear in arbitrary order:

     END {
         sort = "sort"
         for (key in data) {
             # Sort words with same key
             nwords = asorti(data[key], words)
             if (nwords == 1)
                 continue

             # And print. Minor glitch: trailing space at end of each line
             for (j = 1; j <= nwords; j++)
                 printf("%s ", words[j]) | sort
             print "" | sort
         }
         close(sort)
     }

   Here is some partial output when the program is run:

     $ gawk -f anagram.awk /usr/share/dict/words | grep '^b'
     ...
     babbled blabbed
     babbler blabber brabble
     babblers blabbers brabbles
     babbling blabbing
     babbly blabby
     babel bable
     babels beslab
     babery yabber
     ...