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

   DATA DEFINITIONS: 
   word   = list[Thing]
   
   permutations : word -> list[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)
  (cond
    ((empty? l) (list empty))
    (else
     (insert-at-all-positions/in-all-permutations (first l) 
						  (permutations (rest 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)
  (cond
    ((empty? loperms) empty)
    (else (append (insert-at-all-positions a (first loperms))
		  (insert-at-all-positions/in-all-permutations a (rest loperms))))))

;; insert-at-all-positions : Thing 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)
  (cond
    ((empty? loperm) empty)
    (else (cons (cons a (first loperm)) (add-to-front a (rest 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)
	    (cond
	      ((empty? set1) #t)
	      (else (and (member? (first set1) set2)
			 (subset? (rest set1) set2)))))
	  (define (member? a-thing set2)
	    (cond
	      ((empty? set2) #f)
	      (else (or (thing-equality? a-thing (first set2))
			(member? a-thing (rest 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)))

|#