[plt-scheme] Permutations (newbie)

From: Andrew Kesery (andrew.kesery at gmail.com)
Date: Sun Sep 17 13:04:58 EDT 2006

Hello all,

Out of curiosity, I'm teaching myself Scheme using HTDP. Chapter 12 contains an
exercise where you're supposed to take a list of symbols and return a list of
all possible permutations of those symbols. 

After a lot of messing around I've found a way to make it work, but it left me
feeling it can't be the best solution. It's quite verbose compared to a
reference implementation I did in Python at a point when I was beginning to
doubt my intellectual prowess :). 

I'd appreciate feedback regarding possible improvements.

Here is the code:

(define (insert-in-word-with-prefix prefix s word) ; like insert-in-word, but
with a prefix
   (append (append prefix (list s)) word)
     [(not (empty? word)) 
      (insert-in-word-with-prefix (append prefix (list (first word)))
                                  (rest word))]
     [else (list)])))

(define (insert-in-word s word) ; put s in all possible positions in word
  (cons (cons s word)
        (insert-in-word-with-prefix (list (first word)) 
                                    (rest word))))

(insert-in-word 'x (list 'a 'b 'c)) ; test

(define (insert-in-words s words) ; runs insert-in-word for all words
    [(empty? words) (list)]
     (append (insert-in-word s (first words))
             (insert-in-words s (rest words)))]))

(define (permutations symbols)
    [(empty? symbols) empty]
    [(empty? (rest symbols)) (list symbols)]
    [else (insert-in-words (first symbols) 
                           (permutations (rest symbols)))]))

(permutations (list 'a 'b 'c))


Posted on the users mailing list.