普通 lisp 中的整数分区

Question

我正在移植一个函数，它接受一个整数并吐出该数字的整数分区，即

(partitions 4)

应该产生

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

也就是说，分区列表首先按最大部分进行 lex 排序，然后是第二大部分，依此类推。总和就是我们要分区的整数。

在 John Stembridge 的 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))))

我想要它 return ((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是由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...)...) 在 Lisp 中是不常见的。 IF 通常是 returns 一个值，因此不需要使用 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 在 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))))))

普通 lisp 中的整数分区

Integer partitions in common lisp

common-lisp

maple