Set operations in Common Lisp

set-operations.lisp

(defun powerset (list)
  "powerset returns the list of sublists of list"
  (reduce #'(lambda (e l)
              (nconc (mapcar #'(lambda (l) (cons e l)) l)
                     l))
          list
          :from-end t
          :initial-value '(nil)))

(defun permutation (list)
  "permutation returns a list of permutations of list"
  (labels ((helper (acc front el back end-p)
             (if end-p 
               acc
               (let ((permu (permutation (append front back))))
                 (helper (nconc acc
                                (mapcar #'(lambda (l) (cons el l)) permu))
                         (nconc front (list el))
                         (car back)
                         (cdr back)
                         (null back))))))
    (if (or (null list) (null (cdr list)))
      (list list)
      (helper () () (car list) (cdr list) nil))))

(defun combination (list k)
  "combination returns a list of k-combinations of list"
  (delete-if-not
    #'(lambda (l) (= (length l) k))
    (reduce #'(lambda (e acc)
                (delete-if-not #'(lambda (e) (<= (length e) k))
                               (nconc (mapcar #'(lambda (acc) (cons e acc)) acc)
                                      acc)))
            list
            :from-end t
            :initial-value '(nil))))