I have written about partitions before. Today, I am going to write a lisp function that returns all partitions of a fixed number of a certain size.
Let us recall: an \(k\)-partition of a positive integer \(n\) is an ordered sequence of integers \(1≤n_1≤⋯≤n_k\) such that \(\sum_i n_i=n\).
Let us relax the condition that \(n_1≥1\) and allow \(n_1≥0\).
In any case, notice that the first term in the sequence \(n_1\) can not be greater than \(⌊\frac{n}{k}⌋\) because otherwise the sum would be greater than \(n\) necessarily.
Also, notice that if \(k≥n\) then our partition must have at least \(k−n\) zeros in it.
And finally, if \(0≤n_1≤⋯≤n_k\) is a \(k\)-partition of \(n\), then \(n_2−n_1≤n_3−n_1≤⋯≤n_k−n_1\) is a \(k−1\)-partition of \(n−k⋅n\).
Using these observations, we can now write a recursive function:
(defun partitions-with-zeros (n k &optional (a 0) acc)
(cond
((< n 0) nil)
((> k n) (partitions-with-zeros n (1- k) a (cons a acc)))
((= k 1) (list (reverse (cons (+ n a) acc))))
((= n 0) (list (append (reverse acc) (loop repeat k collect a))))
(t (loop for i from (floor n k) downto 0 append
(partitions-with-zeros (- n (* k i)) (1- k) (+ a i) (cons (+ a i) acc))))))
PARTITIONS-WITH-ZEROSLet us test:
(partitions-with-zeros 12 5)
((2 2 2 3 3) (2 2 2 2 4) (1 2 3 3 3) (1 2 2 3 4) (1 2 2 2 5) (1 1 3 3 4)
(1 1 2 4 4) (1 1 2 3 5) (1 1 2 2 6) (1 1 1 4 5) (1 1 1 3 6) (1 1 1 2 7)
(1 1 1 1 8) (0 3 3 3 3) (0 2 3 3 4) (0 2 2 4 4) (0 2 2 3 5) (0 2 2 2 6)
(0 1 3 4 4) (0 1 3 3 5) (0 1 2 4 5) (0 1 2 3 6) (0 1 2 2 7) (0 1 1 5 5)
(0 1 1 4 6) (0 1 1 3 7) (0 1 1 2 8) (0 1 1 1 9) (0 0 4 4 4) (0 0 3 4 5)
(0 0 3 3 6) (0 0 2 5 5) (0 0 2 4 6) (0 0 2 3 7) (0 0 2 2 8) (0 0 1 5 6)
(0 0 1 4 7) (0 0 1 3 8) (0 0 1 2 9) (0 0 1 1 10) (0 0 0 6 6) (0 0 0 5 7)
(0 0 0 4 8) (0 0 0 3 9) (0 0 0 2 10) (0 0 0 1 11) (0 0 0 0 12))Well, the solution above is not exactly what I want. I want partitions without zeros. For that we observe that if \(n_1≤⋯≤n_k\) is a \(k\)-partition of \(n\), then for each \(a≥1\), the sequence \(a≤a+n_1≤⋯≤a+n_k\) is a \(k+1\)-partition of \(n+k⋅a\). Thus
(defun partitions (n k)
(partitions-with-zeros (- n k) k 1))
PARTITIONSLet us test:
(partitions 12 5)
((2 2 2 3 3) (2 2 2 2 4) (1 2 3 3 3) (1 2 2 3 4) (1 2 2 2 5) (1 1 3 3 4)
(1 1 2 4 4) (1 1 2 3 5) (1 1 2 2 6) (1 1 1 4 5) (1 1 1 3 6) (1 1 1 2 7)
(1 1 1 1 8))