Skip to content

Instantly share code, notes, and snippets.

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
(define (permutations ls)
;; 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)))]
;; 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))
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.