;; ------------------------------------------
;;            John Paxton
;;        September 21, 2004
;;             CS 436
;; ------------------------------------------
;; Program 1 Solution
;; ------------------------------------------

;; ------------------------------------------
;; selection-sort
;; ------------------------------------------
;; alist: a list of unique integers
;; ------------------------------------------
;; This function prints out the original list,
;; sorts it into ascending order using selection
;; sort, and then prints out the sorted list.
;; ------------------------------------------

(defun selection-sort ( alist )
  (format t "~%The original list was: ~a~%" alist)
  (do
    ((result nil)   ;; the sorted list
      element       ;; the largest number left in the list
    )
    ((null alist) (format t "The sorted list is ~a~%" result))
      (setf element (apply #'max alist))
      (setf result (cons element result))
      (setf alist (remove element alist))
  )
)

;; -------------------------------------------
;; permutation
;; -------------------------------------------
;; number: a non-negative integer
;; -------------------------------------------
;; Generate and print the permutations that
;; involve the numbers from 1 .. number in
;; descending lexigraphical order.
;; -------------------------------------------

(defun permutation (number)

  (let
    (
     (to-use nil)   ;; the numbers in the permutation
    )

    (format t "~%The permutations are: ~%~%")

    (dotimes (i number)
      (setf to-use (cons (+ 1 i) to-use))
    )

    (generate nil to-use)
  )
)


;; -------------------------------------------
;; generate 
;; -------------------------------------------
;; used: the numbers already included in the permutation
;; to-use: the numbers that must still be added to the permutation
;; -------------------------------------------
;; Generate and print the permutations.
;; -------------------------------------------

(defun generate (used to-use)
  (if (null to-use) 
      (format t "~a~%" used)
      (dolist (current to-use)
        (generate (append used (list current)) (remove current to-use))
      )
  )
)