# 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>
```