;;  Comp210 hw5 solution
;;  Ian Barland, 96.Oct.03


;;-------------------- 3. arrangements --------------------
;;
;; The whole program can be derived with the plain recipe.
;; It requires neither accumulator recursion nor generative recursion.

;; The function arrangements
;;   accepts a list l
;;   returns a list of all possible arrangements (permutations) of l
;;
(define arrangements
  (lambda (l)
    (cond
      ((null? l) (cons null null))
      (else (insert-at-all-positions/in-all-lists
	     (car l) 
	     (arrangements (cdr l)))))))


;; The function insert-at-all-positions/in-all-lists
;;   accepts an element a and a list of lists lol
;;   returns lol such that a occurs
;;     in all positions in all elements of lol
;; Example:
;;    if a = 9 and lol = (list (list 1 2) (list 3 4))
;;    then the result is
;;     (list (list 9 1 2) (list 1 9 2) (list 1 2 9)
;;           (list 9 3 4) (list 3 9 4) (list 3 4 9))
;; If lol contains N lists with M elements each,
;; the result is a list of lists with N * (M+1) elements. 
;;
(define insert-at-all-positions/in-all-lists
  (lambda (a lol)
    (cond
      ((null? lol) null)
      (else (append
	     (insert-at-all-positions a (car lol))
	     (insert-at-all-positions/in-all-lists a (cdr lol)))))))


;; The function  insert-at-all-positions
;;   accepts an element a and a list alist
;;   returns a list of lists such that each element
;;     is like alist with a inserted at some position
;;   together all elements in the results are such that a
;;   is inserted at all possible positions (0, 1, 2, ..., end) of alist.
;; Example:
;;   If a = 9 and alist = (list 1 2)
;;   then the result is (list (list 9 1 2) (list 1 9 2) (list 1 2 9)).
;;
(define insert-at-all-positions
  (lambda (a alist)
    (cond
      ((null? alist) (list (cons a null)))
      (else (cons (cons a alist)
                  (add-first-back
		   (car alist)
		   (insert-at-all-positions a (cdr alist))))))))


;; The function add-first-back
;;    accepts an element a and a list of lists lol
;;    returns a list of lists like lol with a added as the first
;;    element to each list in lol. 
;;
(define add-first-back
  (lambda (a ll)
    (cond
      ((null? ll) null)
      (else (cons (cons a (car ll))
		  (add-first-back a (cdr ll)))))))

;; An Example:
(define R (arrangements (list 1 2 3)))