mississippi-triplets


How many distinct three-letter combinations can you make from the letters of Mississippi? This is Exercise 2.2-16 from The Art of Probability.

 (define (clear bag elt) 
  
   ; Return a copy of the given non-empty bag.  The copy contains one less  
   ; instance of the given element if possible; otherwise the copy is  
   ; identical to the original. 
  
   (let loop ((pre '()) (c (car bag)) (post (cdr bag))) 
     (if (char=? elt c) 
       (append pre post) 
       (let ((pre' (cons c pre))) 
         (if (null? post) 
           pre' 
           (loop pre' (car post) (cdr post))))))) 
  
  
 (define (mis) 
  
   ; Return a set containing all letter triples found in the word 
   ; "mississippi". 
  
   (let ((word '(#\m #\i #\s #\s #\i #\s #\s #\i #\p #\p #\i)) 
         (triplets (make-hash-table 101))) 
     (for-each 
       (lambda (c1) 
         (let ((word' (clear word c1))) 
           (for-each 
             (lambda (c2) 
               (for-each 
                  (lambda (c3) 
                    (hash-set! triplets (list->string (list c1 c2 c3)) 1)) 
                  (clear word' c2))) 
             word'))) 
       word) 
     (hash-fold (lambda (k v s) (cons k s)) '() triplets))) 
  
 guile> (length (mis)) 
 53 
  
 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") 
  
 guile>  

First generalization: allow any word.

 (define (mis word) 
  
   ; Return a set containing all letter triples found in the given word. 
  
   (let ((letters (string->list word)) 
         (triplets (make-hash-table 101))) 
     (for-each 
       (lambda (c1) 
         (let ((letters' (clear letters c1))) 
           (for-each 
             (lambda (c2) 
               (for-each 
                  (lambda (c3) 
                    (hash-set! triplets (list->string (list c1 c2 c3)) 1)) 
                  (clear letters' c2))) 
             letters'))) 
       letters) 
     (hash-fold (lambda (k v s) (cons k s)) '() triplets))) 
  
 guile> (length (mis "mississippi")) 
 53 
  
 guile> (sort (mis "mississippi") 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") 
  
 guile> (length (mis "banana")) 
 19 
  
 guile> (sort (mis "banana") string<) 
 ("aaa" "aab" "aan" "aba" "abn" "ana" "anb" "ann" "baa" "ban" "bna" "bnn" 
  "naa" "nab" "nan" "nba" "nbn" "nna" "nnb") 
  
 guile> 

category-code