Friday, June 17, 2011

Exercise 2.2-16

How many distinct three-letter combinations (“words”) can you make from the letters of Mississippi?

The answer given is 38, but consider all words with an m. Each of the other letters can be one of i, p, or s for \(3\cdot3 = 9\) words. There are three possible positions for m, giving \(3\cdot9 = 27\) words containing an m.

There are \(3! = 6\) words containing each of the letters i, p, and s.

For each word containing a pair of is, the remaining letter can be p or s, and the letter can appear in one of three positions, for 6 words containing two is. Words containing a pair of ps or a pair of ss have the same count, giving \(3\cdot6 = 18\) words containing letter pairs.

Finally, there are two words containing three identical letters? giving \(27 + 6 + 18 + 2 = 53\) distinct three-letter words.

As a check, here’s two Scheme functions computing the same value:
guile> (define (clear bag char)

  ; Return a copy of bag with an instance of char removed.

  (let loop ((pre '()) (c (car bag)) (post (cdr bag)))
    (if (char=? char c) 
      (append pre post)
      (let ((pre' (cons c pre)))
        (if (null? post)
          (append pre' post)
          (loop pre' (car post) (cdr post)))))))

guile> (define (mis)                                                                   
  ; Return a set containing all three-letter combinations                      
  ; from the word "mississippi".                                                
  (let ((word '(#\m #\i #\s #\s #\i #\s #\s #\i #\p #\p #\i))                   
       (triplets (make-hash-table 101)))                                        
      (lambda (c1)                                                              
        (let ((word' (clear word c1)))                                          
            (lambda (c2)                                                        
                (lambda (c3)                                                    
                    triplets (list->string (list c1 c2 c3)) 1))        
                (clear word' c2)))                                              
    (hash-fold (lambda (k v s) (cons k s)) '() triplets)))                      

guile> (length (mis))

guile> (sort (mis) string<)
("iii" "iim" "iip" "iis" "imi" "imp" "ims" "ipi" "ipm" "ipp"
 "ips" "isi" "ism" "isp" "iss" "mii" "mip" "mis" "mpi" "mpp"
 "mps" "msi" "msp" "mss" "pii" "pim" "pip" "pis" "pmi" "pmp"
 "pms" "ppi" "ppm" "pps" "psi" "psm" "psp" "pss" "sii" "sim"
 "sip" "sis" "smi" "smp" "sms" "spi" "spm" "spp" "sps" "ssi"
 "ssm" "ssp" "sss")