Assume \(A\) is a finite set. Today, I would like to write a lisp function that returns the set of all partitions of \(A\).
For an element \(x\in A\), assume we constructed the set of all partitions of \(A\setminus \{x\}\). Then for any partition \(p\) of \(A\setminus\{x\}\), the set \(p\cup \{\{x\}\}\) is a partition of \(A\). Moreover, if \(p = \{ a_1,\ldots,a_k \}\) is a partition of \(A\setminus \{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
EndHere 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))))))PARTITIONSLet 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))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))))))