2008年11月16日 星期日

LISP Practice

Quick-sort


(defmacro for-all (x op xs)
`(remove-if-not #'(lambda (y) (,op y x)) xs))

(defun qsort (nums)
(if (not nums)
()

(let ((x (first nums))
(xs (rest nums)))
(if (eq x nil)
()

(append
(qsort (for-all x < xs))
(list x)
(qsort (for-all x >= xs)))))))


Permutation

(defun remove-first (n nums)
(remove n nums :count 1))

(defun join-sublists (superlist)
(reduce #'(lambda (l1 l2) (append l1 l2)) superlist))

(defun permute-sorted-list (nums perm)
(if (eq nums nil)
(list perm)

(let ((unique-nums (remove-duplicates nums))) (join-sublists
(mapcar (lambda (n)
(permute-sorted-list (remove-first n nums) (append perm (list n))))
unique-nums)))))

(defun permutation (nums)
(permute-sorted-list (sort nums #'<) '()))
張貼留言