permutations.rkt

;; permutations: takes a list and returns a list of lists,
;; where each is a permutation of the original.
;; I got the idea for the algorithm from http://stackoverflow.com/a/23718676/415518.
(define (permutations ls)
  (cond
    ;; base cases: lists of length 0, 1, or 2
    [(null? ls) '(())]
    [(equal? (length ls) 1) `((,(first ls)))]
    [(equal? (length ls) 2)
     `((,(first ls) ,(second ls))
       (,(second ls) ,(first ls)))]
    [else
     ;; For every element in ls,
     (concatenate (map (lambda (elem)
                    ;; create a sublist with that element removed, and get
                    ;; all permutations of the sublist,
                    (let* ([sublist (stream->list (remove-first ls elem equal?))]
                           [perms (permutations sublist)])
                      ;; then re-add the removed element to each of those.
                      (map (lambda (l)
                             (cons elem l))
                           perms)))
                  ls))]))