All partitions of an integer

Description of the problem

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\).

A first pass

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-ZEROS

Let 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))

A second pass

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))

PARTITIONS

Let 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))