Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
;; 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))]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.