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>