#| ----------------------------------------------------------------------------
   Permutations

   DATA DEFINITIONS: 
   word   = (listof Thing)
   
   permutations : word -> (listof word) 
   (define (permutations a-word) ...)
   
   PURPOSE: compute a list of all words that are re-arrangements of Things in a-word
   the ordering of the words in the result doesn't matter

   EXAMPLES: 
   (permutations empty) 
   = 
   empty
   
   (permutations (list 'a))
   = 
   (list (list 'a))
   
   (permutations (list 'a 'b))
   = 
   (list (list 'a 'b) (list 'b 'a))

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

   -------------------------------------------------------------------------
|#

(define (permutations l)
  (foldr insert-at-all-positions/in-all-permutations
	 (list empty)
	 l))

;; insert-at-all-positions/in-all-permutations : Thing list[word] -> list[word]
;; Purpose: produces a list of words with a inserted in between all Things
;;   and at the beginning and the end of each word on loperms; 
(define (insert-at-all-positions/in-all-permutations a loperms)
  (foldr append
	 empty
	 (map (lambda (x) (insert-at-all-positions a x))
	      loperms)))

;; insert-at-all-positions : Thing list[word] -> list[word]
;; Purpose: produce list of all words such that a is added in a position in word
(define (insert-at-all-positions a a-perm)
  (cond
    ((empty? a-perm) (list (cons a empty)))
    (else (cons (cons a a-perm)
		(add-to-front (first a-perm)
		              (insert-at-all-positions a (rest a-perm)))))))

;; add-to-front : Thing list[word] -> list[word]
;; Purpose: produce list of words with a added to the front of each word on loperm
(define (add-to-front a loperm)
  (map (lambda (x) (cons a x))
       loperm))

#|
------------------------------------------------------------------------------
TESTS: uncomment to test

;; set-equal? : (word word -> bool) set1 set2 -> bool
;; Purpose: determine whether set1 and set2 (represented as lists) ae equal
;;   with respect to thing-equality? 
;; This function is an auxiliary function to simplify testing permutations. 
(define (set-equal? thing-equality? set1 set2)
  (local ((define (set-equal? set1 set2)
	    (and (subset? set1 set2) (subset? set2 set1)))
	  (define (subset? set1 set2)
	    (andmap (lambda (x) (member? x set2))
	            set1))
	  (define (member? a-thing set2)
	    (ormap (lambda (x) (thing-equality? a-thing x))
		   set2))
    (set-equal? set1 set2)))

(set-equal? equal?
	    (permutations (list 'a 'b))
	    (list (list 'a 'b) (list 'b 'a)))

(set-equal? equal? 
	    (permutations (list 'a 'b 'c))
	    (list (list 'a 'b 'c)
		  (list 'a 'c 'b)
		  (list 'b 'a 'c)
		  (list 'c 'b 'a)
		     (list 'b 'c 'a)
		     (list 'c 'a 'b)))

|#