Extended Exercise: Rearranging Words

Newspapers often contain exercises that ask readers to find all possible words made up from some letters. One way to play this game is to form all possible arrangements of the letters in a systematic manner and to see which arrangements are dictionary words. Suppose the letters ``a,'' ``d,'' ``e,'' and ``r'' are given. There are twenty-four possible arrangements of these letters:

The systematic enumeration of all possible arrangements is clearly a task for a computer program. It consumes a word and produces a list of the word's letter-by-letter rearrangements.

One representation of a word is a list of symbols. Each item in the input represents a letter: 'a, 'b, ..., 'z. Here is the data definition for words:

A word is either empty, or (cons a w) where a is a symbol ('a, 'b, ..., 'z) and w is a word.

Exercise 12.4.1

Formulate the data definition for lists of words. Systematically make up examples of words and lists of words. Solution

Let us call the function arrangements. Its template is that of a list-processing function:

;; arrangements : word -> list-of-words
;; to create a list of all rearrangements of the letters in a-word 
(define (arrangements a-word) 
  (cond 
    [(empty? a-word) ...] 
    [else ... (first a-word) ... (arrangements (rest a-word)) ...])) 

Given the contract, the supporting data definitions, and the examples, we can now look at each cond-line in the template:

1. If the input is empty, there is only one possible rearrangement of the input: the empty word. Hence the result is (cons empty empty), the list that contains the empty list as the only item.
2. Otherwise there is a first letter in the word, and (first a-word) is that letter and the recursion produces the list of all possible rearrangements for the rest of the word. For example, if the list is

   (cons 'd (cons 'e (cons 'r empty)))
   

   then the recursion is (arrangements (cons 'e (cons 'r empty))). It will produce the result

   (cons (cons 'e (cons 'r empty))
     (cons (cons 'r (cons 'e empty)) 
       empty)) 
   

   To obtain all possible rearrangements for the entire list, we must now insert the first item, 'd in our case, into all of these words between all possible letters and at the beginning and end.

The task of inserting a letter into many different words requires processing an arbitrarily large list. So, we need another function, call it insert-everywhere/in-all-words, to complete the definition of arrangements:

(define (arrangements a-word)
  (cond 
    [(empty? a-word) (cons empty empty)] 
    [else (insert-everywhere/in-all-words (first a-word) 
            (arrangements (rest a-word)))])) 

Exercise 12.4.2

Develop the function insert-everywhere/in-all-words. It consumes a symbol and a list of words. The result is a list of words like its second argument, but with the first argument inserted between all letters and at the beginning and the end of all words of the second argument.

Hint: Reconsider the example from above. We stopped and decided that we needed to insert 'd into the words (cons 'e (cons 'r empty)) and (cons 'r (cons 'e empty)). The following is therefore a natural candidate:

(insert-everywhere/in-all-words 'd
  (cons (cons 'e (cons 'r empty)) 
    (cons (cons 'r (cons 'e empty)) 
      empty))) 

Also, use the Scheme operation append, which consumes two lists and produces the concatenation of the two lists. For example:

  (append (list 'a 'b 'c) (list 'd 'e)) 
= (list 'a 'b 'c 'd 'e)