;; 
;; Like item, but returns the same lst with the element
;;  at that index removed
;; 
(define (remove index lst)
  (if (= index 1)
      (cdr lst)
      (cons (car lst) (remove (- index 1) (cdr lst)))))

(define x1 '(1 2 3 4))
(define t1 (list (remove 1 x1)
                 (remove 2 x1)
                 (remove 3 x1)
                 (remove 4 x1)))

;;----------------------------------------


;;
;; Takes an element and a list of lists, and returns a new lst 
;; of those original lists with element appended.
;;
(define (prefix-lists element lsts)
  (if (null? lsts)
      '()
      (cons (cons element (car lsts))
            (prefix-lists element (cdr lsts)))))

(define x2 '((1 2 3) (1) () (1 2 3)))
(define t2 (prefix-lists 9 x2))

;;-----------------------------------------
;;
;; Returns a list of all the possible permutations of 
;;  the elements of lst

(define (permutations lst)
  (permute lst 1))

(define (permute lst index)
  (cond ((= (count lst) 1) (list lst)) ;; know 1-element permutes
        ((< (count lst) index) '())    ;; recursive base case
        (else ;; prefix the current element onto all of the
              ;; (recursive) permutations with that element 
              ;; removed, and append that to the (recursive)
              ;; permtuations of the next index.
         (append (prefix-lists (item index lst)
                                    (permute (remove index lst)
                                             1))
                      (permute lst (+ index 1))))))

(define x3 '(1))
(define x4 '(1 2))
(define x5 '(1 2 3))
(define x6 '(1 2 3 4))
(define x7 '(1 1 2 2 3 3))


(define t3 (permutations x3))
(define t4 (permutations x4))
(define t5 (permutations x5))
(define t6 (permutations x6))
(define t7 (permutations x7))