I'm porting a function that takes in an integer and spits out the integer partitions of that number, that is
(partitions 4)
should yield
((4) (3 1) (2 2) (2 1 1) (1 1 1 1))
that is, partition lists are lex-sorted first by largest part, then second-largest part, etc. And the sum is the integer we are partitioning.
In the maple package SF by John Stembridge this is produced by the following subroutine that produces the partitions with diagram within a box defined by row and col so that SF/Par/sub(n,n,n) is what I want:
`SF/Par/sub`:=proc(n,row,col) local i;
if n=0 then [[]]
elif col=0 then []
else
[seq(op(map((x,y)->[y,op(x)],`SF/Par/sub`(n+i,-i,col-1),-i)),
i=-min(row,n)..-iquo(n+col-1,col))]
fi
end:
where iquo is (floor (/ x y))
The question is how to get from
(2 (2 ()) (1 (1 ())))
the result
((2 2) (2 1 1))
?
Edit
The following is my attempt
(defun partitions (n row col)
""
(block nil
(if (= n 0) (return '(())))
(if (= col 0) (return '()))
(loop for i from (- (min row n)) to (floor (/ (- (+ n col) 1) col))
collect (cons (- i) (partitions (+ n i) (- i) (- col 1))))))
It runs and terminates but that's all I can say for it.
(partitions 3 3 3) yields
((3 NIL) (2 (1 NIL) (0 (0) (-1)) (-1 (-1) (-2))) (1 (1 (1 NIL) (0) (-1)) (0 (0) (-1) (-2)) (-1 (-1) (-2) (-3))) (0 (0 (0) (-1) (-2) (-3)) (-1 (-1) (-2) (-3) (-4)) (-2 (-2) (-3) (-4) (-5))) (-1 (-1 (-1) (-2) (-3) (-4) (-5)) (-2 (-2) (-3) (-4) (-5) (-6))))
I want it to return ((3) (2 1) (1 1 1))
You should use COND instead of BLOCK/RETURN
(defun partitions (n row col)
(cond ((= n 0) ...)
((= col 0) ...)
(t (loop ...))))
Then you could use ZEROP instead of (= X 0), and 1- instead of (- X 1). I don't see any reason to make I negative either (you can use the loop keyword DOWNTO to count down). FLOOR takes a divisor as an optional argument, so you can write (FLOOR X Y) instead of (FLOOR (/ X Y)).
With these changes:
(defun partitions (n row col)
""
(cond ((zerop n) '(()))
((zerop col) '())
(t (loop for i from (min row n) downto (floor (1- (+ n col)) col)
collect (cons i (partitions (- n i) i (1- col)))))))
(partitions 3 3 3)
;=> ((3 NIL) (2 (1 NIL)) (1 (1 (1 NIL))))
Those NILs are caused by the nested list in the first clause of the COND. Remember that an empty list is the same as NIL. If you change it to just '(), the result will be ((3) (2 (1)) (1 (1 (1)))).
To get rid of those extra inner lists, you could use an inner function that builds the result and pushes it into a list when N is zero.
(defun partitions (n row col)
""
(let ((result (list)))
(labels ((%partitions (n row col acc)
(cond ((zerop n) (push (reverse acc) result))
((zerop col))
(t (loop for i from (min row n) downto (floor (1- (+ n col)) col)
do (%partitions (- n i) i (1- col) (cons i acc)))))))
(%partitions n row col '())
(nreverse result))))
(partitions 3 3 3)
;=> ((3) (2 1) (1 1 1))
(partitions 4 4 4)
;=> ((4) (3 1) (2 2) (2 1 1) (1 1 1 1))
A bit longer, but, at least IMO, simpler way to solve the problem:
(defun partitions (n)
(let ((result (list)))
(labels ((%partitions (n largest-number acc)
(cond ((< n 1) (push (reverse acc) result))
(t (loop for l from largest-number downto 1
do (loop for i from (floor n l) downto 1
do (%partitions
(- n (* l i))
(1- l)
(append (make-list i :initial-element l)
acc))))))))
(%partitions n n '())
(nreverse result))))
(partitions 3)
;=> ((3) (2 1) (1 1 1))
(partitions 4)
;=> ((4) (3 1) (2 2) (2 1 1) (1 1 1 1))
(partitions 5)
;=> ((5) (4 1) (3 2) (3 1 1) (2 2 1) (2 1 1 1) (1 1 1 1 1))