Set of All Partitions of a Finite Set

Description of the problem

Assume $A$ is a finite set. Today, I would like to write a lisp function that returns the set of all partitions of $A$ .

An algorithm

For an element $x \in A$ , assume we constructed the set of all partitions of $A ∖ {x}$ . Then for any partition $p$ of $A ∖ {x}$ , the set $p \cup {{x}}$ is a partition of $A$ . Moreover, if $p = {a_{1}, \dots, a_{k}}$ is a partition of $A ∖ {x}$ then each $p_{i}$ obtained from $p$ by replacing $a_{i}$ with $a_{i} \cup {x}$ is another partition of $A$ .

 Algorithm Partitions
 Input: A finite set A
 Output: Set of all partitions of A
 Initialize: Result <- {}
 Begin
   If A is empty or A contains a single element
      Return { A }
   Else
      Pick an element x from A
      P <- Partitions( A \ {x} )
      For each V in P:
          Add { V, {x} } to Result
          For each v in V
              Let W be a copy of V
              Add x to the copy of v in W
              Add W to Result
          End
      End
    End
    Return Result
 End

An implementation in common lisp

Here is an implementation of the algorithm above in Common Lisp:

(defun partitions (xs)
  (labels
      ((insert (ys)
         (let ((x (car xs))
               (res nil))
           (cons (cons (list x) ys)
                 (dotimes (i (length ys) res)
                   (let ((zs (copy-list ys)))
                     (push x (elt zs i))
                     (push zs res)))))))
    (if (= 1 (length xs))
        (list (list xs))
        (mapcan #'insert (partitions (cdr xs))))))

PARTITIONS

Let us test:

(format nil "~{~a~%~}" (partitions '(0 1 2 3 4 5)))

((0) (1) (2) (3) (4) (5))
((1) (2) (3) (4) (0 5))
((1) (2) (3) (0 4) (5))
((1) (2) (0 3) (4) (5))
((1) (0 2) (3) (4) (5))
((0 1) (2) (3) (4) (5))
((0) (2) (3) (4) (1 5))
((2) (3) (4) (0 1 5))
((2) (3) (0 4) (1 5))
((2) (0 3) (4) (1 5))
((0 2) (3) (4) (1 5))
((0) (2) (3) (1 4) (5))
((2) (3) (1 4) (0 5))
((2) (3) (0 1 4) (5))
((2) (0 3) (1 4) (5))
((0 2) (3) (1 4) (5))
((0) (2) (1 3) (4) (5))
((2) (1 3) (4) (0 5))
((2) (1 3) (0 4) (5))
((2) (0 1 3) (4) (5))
((0 2) (1 3) (4) (5))
((0) (1 2) (3) (4) (5))
((1 2) (3) (4) (0 5))
((1 2) (3) (0 4) (5))
((1 2) (0 3) (4) (5))
((0 1 2) (3) (4) (5))
((0) (1) (3) (4) (2 5))
((1) (3) (4) (0 2 5))
((1) (3) (0 4) (2 5))
((1) (0 3) (4) (2 5))
((0 1) (3) (4) (2 5))
((0) (3) (4) (1 2 5))
((3) (4) (0 1 2 5))
((3) (0 4) (1 2 5))
((0 3) (4) (1 2 5))
((0) (3) (1 4) (2 5))
((3) (1 4) (0 2 5))
((3) (0 1 4) (2 5))
((0 3) (1 4) (2 5))
((0) (1 3) (4) (2 5))
((1 3) (4) (0 2 5))
((1 3) (0 4) (2 5))
((0 1 3) (4) (2 5))
((0) (1) (3) (2 4) (5))
((1) (3) (2 4) (0 5))
((1) (3) (0 2 4) (5))
((1) (0 3) (2 4) (5))
((0 1) (3) (2 4) (5))
((0) (3) (2 4) (1 5))
((3) (2 4) (0 1 5))
((3) (0 2 4) (1 5))
((0 3) (2 4) (1 5))
((0) (3) (1 2 4) (5))
((3) (1 2 4) (0 5))
((3) (0 1 2 4) (5))
((0 3) (1 2 4) (5))
((0) (1 3) (2 4) (5))
((1 3) (2 4) (0 5))
((1 3) (0 2 4) (5))
((0 1 3) (2 4) (5))
((0) (1) (2 3) (4) (5))
((1) (2 3) (4) (0 5))
((1) (2 3) (0 4) (5))
((1) (0 2 3) (4) (5))
((0 1) (2 3) (4) (5))
((0) (2 3) (4) (1 5))
((2 3) (4) (0 1 5))
((2 3) (0 4) (1 5))
((0 2 3) (4) (1 5))
((0) (2 3) (1 4) (5))
((2 3) (1 4) (0 5))
((2 3) (0 1 4) (5))
((0 2 3) (1 4) (5))
((0) (1 2 3) (4) (5))
((1 2 3) (4) (0 5))
((1 2 3) (0 4) (5))
((0 1 2 3) (4) (5))
((0) (1) (2) (4) (3 5))
((1) (2) (4) (0 3 5))
((1) (2) (0 4) (3 5))
((1) (0 2) (4) (3 5))
((0 1) (2) (4) (3 5))
((0) (2) (4) (1 3 5))
((2) (4) (0 1 3 5))
((2) (0 4) (1 3 5))
((0 2) (4) (1 3 5))
((0) (2) (1 4) (3 5))
((2) (1 4) (0 3 5))
((2) (0 1 4) (3 5))
((0 2) (1 4) (3 5))
((0) (1 2) (4) (3 5))
((1 2) (4) (0 3 5))
((1 2) (0 4) (3 5))
((0 1 2) (4) (3 5))
((0) (1) (4) (2 3 5))
((1) (4) (0 2 3 5))
((1) (0 4) (2 3 5))
((0 1) (4) (2 3 5))
((0) (4) (1 2 3 5))
((4) (0 1 2 3 5))
((0 4) (1 2 3 5))
((0) (1 4) (2 3 5))
((1 4) (0 2 3 5))
((0 1 4) (2 3 5))
((0) (1) (2 4) (3 5))
((1) (2 4) (0 3 5))
((1) (0 2 4) (3 5))
((0 1) (2 4) (3 5))
((0) (2 4) (1 3 5))
((2 4) (0 1 3 5))
((0 2 4) (1 3 5))
((0) (1 2 4) (3 5))
((1 2 4) (0 3 5))
((0 1 2 4) (3 5))
((0) (1) (2) (3 4) (5))
((1) (2) (3 4) (0 5))
((1) (2) (0 3 4) (5))
((1) (0 2) (3 4) (5))
((0 1) (2) (3 4) (5))
((0) (2) (3 4) (1 5))
((2) (3 4) (0 1 5))
((2) (0 3 4) (1 5))
((0 2) (3 4) (1 5))
((0) (2) (1 3 4) (5))
((2) (1 3 4) (0 5))
((2) (0 1 3 4) (5))
((0 2) (1 3 4) (5))
((0) (1 2) (3 4) (5))
((1 2) (3 4) (0 5))
((1 2) (0 3 4) (5))
((0 1 2) (3 4) (5))
((0) (1) (3 4) (2 5))
((1) (3 4) (0 2 5))
((1) (0 3 4) (2 5))
((0 1) (3 4) (2 5))
((0) (3 4) (1 2 5))
((3 4) (0 1 2 5))
((0 3 4) (1 2 5))
((0) (1 3 4) (2 5))
((1 3 4) (0 2 5))
((0 1 3 4) (2 5))
((0) (1) (2 3 4) (5))
((1) (2 3 4) (0 5))
((1) (0 2 3 4) (5))
((0 1) (2 3 4) (5))
((0) (2 3 4) (1 5))
((2 3 4) (0 1 5))
((0 2 3 4) (1 5))
((0) (1 2 3 4) (5))
((1 2 3 4) (0 5))
((0 1 2 3 4) (5))
((0) (1) (2) (3) (4 5))
((1) (2) (3) (0 4 5))
((1) (2) (0 3) (4 5))
((1) (0 2) (3) (4 5))
((0 1) (2) (3) (4 5))
((0) (2) (3) (1 4 5))
((2) (3) (0 1 4 5))
((2) (0 3) (1 4 5))
((0 2) (3) (1 4 5))
((0) (2) (1 3) (4 5))
((2) (1 3) (0 4 5))
((2) (0 1 3) (4 5))
((0 2) (1 3) (4 5))
((0) (1 2) (3) (4 5))
((1 2) (3) (0 4 5))
((1 2) (0 3) (4 5))
((0 1 2) (3) (4 5))
((0) (1) (3) (2 4 5))
((1) (3) (0 2 4 5))
((1) (0 3) (2 4 5))
((0 1) (3) (2 4 5))
((0) (3) (1 2 4 5))
((3) (0 1 2 4 5))
((0 3) (1 2 4 5))
((0) (1 3) (2 4 5))
((1 3) (0 2 4 5))
((0 1 3) (2 4 5))
((0) (1) (2 3) (4 5))
((1) (2 3) (0 4 5))
((1) (0 2 3) (4 5))
((0 1) (2 3) (4 5))
((0) (2 3) (1 4 5))
((2 3) (0 1 4 5))
((0 2 3) (1 4 5))
((0) (1 2 3) (4 5))
((1 2 3) (0 4 5))
((0 1 2 3) (4 5))
((0) (1) (2) (3 4 5))
((1) (2) (0 3 4 5))
((1) (0 2) (3 4 5))
((0 1) (2) (3 4 5))
((0) (2) (1 3 4 5))
((2) (0 1 3 4 5))
((0 2) (1 3 4 5))
((0) (1 2) (3 4 5))
((1 2) (0 3 4 5))
((0 1 2) (3 4 5))
((0) (1) (2 3 4 5))
((1) (0 2 3 4 5))
((0 1) (2 3 4 5))
((0) (1 2 3 4 5))
((0 1 2 3 4 5))

An implementation in clojure

Here is an implementation in clojure:

(defn partitions [xs]
   (letfn [(insert [ys]
              (let [x (first xs)]
                 (cons (conj ys [x])
                       (for [i (range (count ys))]
                          (let [zs (vec ys)]
                             (update zs i conj x))))))]
      (if (= 1 (count xs))
          [[ xs ]]
          (mapcat insert (partitions (rest xs))))))