permutation.rkt

#lang racket
(require racket/match)

;;; permutation: (listof Any) -> (listof (listof Any))
;;; purpose: Consumes a list (alst) and returns all permutations of that list
;;; This is the implementation I came up with on the final
;(define (permutation1 alst)
;  (cond
;    [(= (length alst) 1) alst]
;    [(= (length alst) 2)
;     (list alst (reverse alst))]
;    [else (local
;            [(define (permute-tail p)
;               (local
;                 [(define (consp lst)(cons p lst))
;                  (define (notp elem)(not (equal? p elem)))]
;                 (map consp (permutation1 (filter notp alst)))))]
;            (foldr append empty (map permute-tail alst))
;            )]
;    )
;  )


;; permutation: (listof Any) -> (listof (listof Any))
;; purpose: Consumes a list (alst) and returns all permutations of that list
;; examples:
;;      (perms '()) => '('(empty))
;;      (perms '(1)) => '('(1))
;;      (perms '(1 2)) => '('(1 2) '(2 1))
(define (perms lst)
  (match lst
    [(list x)  (list (list x))]
    [(list x y)(list (list x y)
                     (list y x))]
    [xs (foldr append empty
               (map (λ (x)
                      (map (curry cons x)
                           (perms (remove x xs)))) xs))]
    )
  )

 (perms '(empty))
 (perms '(1))
 (perms '(1 2))