TAOCP 5 Exercise 21

We are given a dictionary of English words.

taocpmathematicsalgorithmsvolume-3medium

Section 5: Introduction to Sorting

Exercise 21. [22] How would you go about looking for five-letter anagrams such as CARET, CARTE, CATER, CRATE, REACT, RECTA, TRACE; CRUEL, LUCRE, ULCER; DOWRY, ROWDY, WORDY? (One might wish to know whether there are any sets of ten or more five-letter English anagrams besides the remarkable set

APERS, ASPER, PARES, PARSE, PEARS, PRASE, PRESA; RAPES, REAPS, SPAER, SPARE, SPEAR,

to which we might add the French word APRÈS.)

Verified: yes
Solve time: 9m08s

Solution

We are given a dictionary of English words. We want to find all sets of five‑letter words that are anagrams of each other (i.e., permutations of the same multiset of letters). In particular, we may wish to determine whether there exist sets of ten or more such words.

Algorithm.

  1. Extract all five‑letter words from the dictionary. Let there be $N$ such words $W_1, W_2, \ldots, W_N$.
  2. For each word $W_j$, compute its canonical form $C_j$, the string obtained by sorting the five letters of $W_j$ into nondecreasing order (e.g., $\mathtt{CARET} \to \mathtt{ACERT}$). Because the length is fixed and the alphabet size is $26$, this can be done in constant time per word, e.g., by a small sorting network or counting sort.
  3. Form $N$ records $(C_j, W_j)$.
  4. Sort these $N$ records lexicographically by $C_j$ as the primary key. (If a stable sort is used, words with the same $C_j$ retain their original relative order; otherwise we may also sort by $W_j$ as a secondary key to obtain a consistent order within each anagram group.)
  5. Scan the sorted list sequentially. Maintain the current canonical form $C$ and a list of words sharing it. For $j = 1$ to $N$:
    • If $C_j \neq C$, the accumulated list is a complete anagram set; output it if its size meets the desired threshold (e.g., $\ge 10$). Then set $C \gets C_j$ and start a new list with $W_j$.
    • Otherwise append $W_j$ to the current list. After the loop, output the final list similarly.

Correctness.
Two words are anagrams iff they contain exactly the same multiset of letters. Sorting the letters produces a unique canonical representation of that multiset. Hence $$W_i \text{ and } W_j \text{ are anagrams} \iff C_i = C_j.$$ After step 4, all records with the same canonical form appear contiguously. The scan in step 5 therefore partitions the list exactly into the equivalence classes of the anagram relation. Every anagram set is found exactly once.

Complexity.
Step 2 takes $O(N)$ time (constant work per word). Step 4 takes $O(N \log N)$ comparisons using any efficient sorting algorithm. Step 5 takes $O(N)$ time. The overall time is $O(N \log N)$, dominated by the sort. The space required is $O(N)$ for the records. If $N$ exceeds internal memory capacity, an external sorting algorithm (e.g., multiway merge sort) can be used, because the problem reduces to sorting a file of fixed‑length records.

This completes the proof. ∎