Целочисленные разделы в common lisp

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

(partitions 4)

должен дать

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

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

В пакете maple SF Джона Стембридж это создается с помощью следующей подпрограммы, которая создает разделы с диаграммой в поле, определяемом 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))


common-lisp maple
person Jan-Magnus Økland    schedule 03.07.2016    source источник
comment
Какой у вас код?   -  person Rainer Joswig    schedule 03.07.2016
comment
@RainerJoswig См. редактирование.   -  person Jan-Magnus Økland    schedule 03.07.2016

Ответы (2)


arrow_upward
3
arrow_downward

Вы должны использовать 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 вызваны вложенным списком в первом предложении 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))
person jkiiski    schedule 03.07.2016

arrow_upward
4
arrow_downward

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

(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 довольно часто встречаются в коде на Лиспе, конструкция 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))))))
person Rainer Joswig    schedule 03.07.2016