分割数 in Elisp

いわゆる「組み合わせ数学」の問題。整数 n を m 以下の整数の和で表す方法が何通りあるかを求めるというもの。考え方は「動的計画法」が参考になる。

単なる再帰で解く

(defun partition-num (n m)
  (cond
   ((or (= n 0) (= m 1)) 1)
   (t (+ (if (>= n m) (partition-num (- n m) m) 0)
         (partition-num n (1- m))))))
=> partition-num
(partition-num 3 3)
=> 3

(partition-num 4 3)
=> 4

(partition-num 9 9)
=> 30

動的計画法的に配列を使って解く

my-make-arrayという関数で多次元配列とそのアクセサみたいな関数を作っている。要するに、Emacs Lisp で多次元配列を使うのは面倒くさいということ。

;;; 多次元配列と、その要素を読み書きする関数（ref, set）を作る関数
;;; 内部的にはデータを1次元配列でもつ。クロージャと連想配列でできている。
(defun my-make-array (&rest dim)
  (lexical-let ((dim dim) (v (make-vector (apply '* dim) 0)))
    (flet ((index (args) (cond
                          ((null dim) 0)
                          (t (+ (* (apply '* (cdr dim)) (car idx))
                                (index (cdr dim) (cdr idx)))))))
      `((ref ,(lambda (&rest args) (elt v (index dim args))))
        (set ,(lambda (val &rest args) (aset v (index dim args) val)))))))
=> my-make-array

;;; 関数を適用する関数
(defun my-call (obj method &rest args)
  (apply (second (assoc method obj)) args))
=> my-call

;;; 配列を使って分割数を解く関数
(defun partition-num-dp (n m)
  (let ((dp (my-make-array (1+ n) (1+ m))))
    (loop for i from 0 to n do
          (loop for j from 1 to m do
                (my-call dp 'set i j
                         (if (or (<= j 1) (zerop i)) 1
                           (+ (my-call dp 'ref i (1- j))
                              (if (>= i j)
                                  (my-call dp 'ref (- i j) j)
                                0))))))
    (my-call dp 'ref n m)))

(partition-num-dp 4 3)
=> 4

(partition-num-dp 9 9)
=> 30