Целых разделы в общей шепелявости

Question

Я портирование функции, которая принимает в целом и выплевывает целые разделы этого числа, то есть

(partitions 4) 

должен давать

((4) (3 1) (2 2) (2 1 1) (1 1 1 1)) 

то есть, списки разделов сначала сортируются по самой большой части, затем второй по величине части и т. д. И сумма представляет собой целое число, которое мы разделяем.

В кленовом пакете SF Джона Stembridge это производится с помощью следующей подпрограммы, которая производит перегородки с диаграммой в окне, определенное row и col, так что SF/Par/sub(n,n,n) является то, что я хочу:

`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: 

где iquo является (floor (/ x y))

вопрос заключается в том, чтобы получить от

(2 (2()) (1 (1()))) 

результат

((2 2) (2 1 1)) 

?

Редактировать

Следующая моя попытка

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

Он работает и заканчивается, но это все, что я могу сказать это.

(partitions 3 3 3) дает

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

Я хочу, чтобы вернуть ((3) (2 1) (1 1 1))

Answer 1

Вы должны использовать COND вместо BLOCK/RETURN

(defun partitions (n row col) 
    (cond ((= n 0) ...) 
     ((= col 0) ...) 
     (t (loop ...)))) 

Тогда вы могли бы использовать ZEROP вместо (= X 0) и 1- в вместо (- X 1). Я не вижу никакой причины делать I отрицательным либо (вы можете использовать ключевое слово цикла DOWNTO для обратного отсчета). FLOOR принимает делитель как необязательный аргумент, поэтому вы можете написать (FLOOR X Y) вместо (FLOOR (/ X Y)).

С учетом этих изменений:

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

Эти NIL s вызваны вложенного списка в первом предложении части COND. Помните, что пустой список совпадает с NIL. Если вы измените его на '(), результатом будет ((3) (2 (1)) (1 (1 (1)))).

Чтобы избавиться от этих дополнительных внутренних списков, вы можете использовать внутреннюю функцию, которая строит результат и вставляет его в список, когда N равен нулю.

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

немного дольше, но, по крайней мере, ИМО, простой способ решить эту проблему:

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

Answer 2

Поскольку у вас уже есть рабочий ответ, вот некоторые комментарии по поводу вашего стиля кодирования:

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

"" может быть опущен, поскольку он бесполезен и не содержит документации.

DEFUN уже устанавливает блок, но он называется partitions. Так

(defun partitions (...) 
    (block nil ... (return ...) ...) 

будет

(defun partitions (...) 
    ... 
    (return-from partitions ...) 
    ...) 

(if (foo) (bar)) часто записываются как (when (foo) (bar)). Потому что (if (foo) (progn (bar) (baz))) является (when (foo) (bar) (baz)).

Использование (block ... (if ... (return ...)) (if ... (return...)...) необычно в Лиспе. IF обычно возвращает значение, поэтому дополнительный поток управления с использованием RETURN или RETURN-FROM не требуется. Вместо

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

можно было бы написать:

(if (= n 0) 
    '(()) 
    (if (= col 0) 
     '() 
    (loop for i from (- (min row n)) to (floor (/ (- (+ n col) 1) col)) 
      collect (cons (- i) (partitions (+ n i) (- i) (- col 1)))))) 

Поскольку эти вложенные If s довольно часто встречаются в Lisp коде, cond конструкция делает его немного легче писать. Код также не будет перемещаться вправо с каждым пунктом:

(cond ((= n 0) 
     '(())) 
     ((= col 0) 
     '()) 
     (t 
     (loop for i from (- (min row n)) to (floor (/ (- (+ n col) 1) col)) 
      collect (cons (- i) (partitions (+ n i) (- i) (- col 1))))))