permutations

[miller@cs.rochester.edu]

here are some helpful functions from CL-LIB (on ftp.cs.rochester.edu,
and Mark K's CMU library, access both from 
http://www.cs.rochester.edu/u/miller/alu.html)

Mark Kantrowitz was the original author of the following functions.

(defun cartesian-product (set1 set2)
  "Returns the cross product of two sets."
  (let ((result ()))
    (dolist (elt1 set1)
      (dolist (elt2 set2)
        (push (cons elt1 elt2) result)))
    result))

(defun cross-product (&rest lists)
  "Returns the cross product of a set of lists."
  (labels ((cross-product-internal (lists)
	     (if (null (cdr lists))
		 (mapcar #'list (car lists))
		 (let ((cross-product (cross-product-internal (cdr lists)))
		       (result '()))
		   (dolist (elt-1 (car lists))
		     (dolist (elt-2 cross-product)
		       (push (cons elt-1 elt-2) result)))
		   result))))
    (cross-product-internal lists)))

(defun permutations (items)
  "Given a list of items, returns all possible permutations of the list."
  (let ((result nil))
    (if (null items)
        '(nil)
        (dolist (item items result)
          (dolist (permutation (permutations (remove item items)))
            (push (cons item permutation) result))))))

(defun powerset (list)
  "Given a set, returns the set of all subsets of the set."
  (let ((result (list nil)))
    (dolist (item list result)
      (dolist (subset result)
	(push (cons item subset) result)))))