最長増加部分列の長さ in Elisp

最長増加部分列（Longest Increasing Subsequence, LIS）の長さを求める問題を、Lisp風に解いただけ。

とりあえず手を動かして例題を解いてみる

これも動的計画法の有名な問題なので、漸化式で考える方法が普通かもしれない。が、自分の場合は例題を手作業で解いているときに頭の中で行っている計算をプログラムに書き直した感じなので、再帰的な解法になっている（空リストのときはゼロ、要素1個のリストの場合は1を返すという前提で開始すれば自然に再帰的な思考になる、はず）。

例題としては Wikipediaに載っていたもの (0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15) を考える。この数列のLISはユニークではなく (0, 2, 6, 9, 13, 15) と (0, 4, 6, 9, 11, 15) の二種類あり、LISの長さは 6。

;; 最後の要素から順番に、各要素を先頭とするLIS長を求めていく。
;; 計算を具体的に手でやってみると、次のような流れになる（リストに作用させる関数をfとおく）。
(f 15) => 1
(f 7 15) => 2              ;7 < 15 なので (f 15) + 1 => 1 + 1
(f 11 7 15) => 2           ;11 < 15 なので (f 15) + 1 => 1 + 1
(f 3 11 7 15) => 3         ;3より大きい11,7,15で始まるLISはそれぞれ長さが2,2,1。maxの2に1加えて3
(f 13 3 11 7 15) => 2      ;13 < 15 なので (f 15) + 1 => 1 + 1
(f 5 13 3 11 7 15) => 3    ;5より大きい13か11か7で始まるLISが最長で2。それに1加えて3
(f 9 5 13 3 11 7 15) => 3  ;9より大きい13か11で始まるLISが最長で2。それに1加えて3
(f 1 9 5 13 3 11 7 15) => 4    ;1より大きい9や5で始まるLISが最長で3。それに1加えて4
(f 14 1 9 5 13 3 11 7 15) => 2    ;14 < 15 なので (f 15) + 1 => 1 + 1
(f 6 14 1 9 5 13 3 11 7 15) => 4  ;6より大きい数のうち、9で始まるLISが最長で3。それに1加えて4
(f 10 6 14 ...略) => 3   ;10より大きい11,13のLISが最長で2。それに1加えて3
(f 2 10 6 ...略) => 5    ;2より大きい6のLISが最長で4。それに1加えて5
(f 12 2 10 ...略) => 3   ;12より大きい13, 14のLISが最長で4。それに1加えて3
(f 4 12 2 ...略) => 5    ;5より大きい数のうち、6で始まるLISが最長で4。それに1加えて5
(f 8 4 12 ...略) => 4    ;8より大きい12,10,9のLISが最長で3。それに1加えて4
(f 0 8 4 ...略) => 6     ;0より大きい数のうち、2で始まるLISが最長で5。それに1加えて6

Elispで

上で書いた解法をEmacs Lisp化する。使っている組み込み関数はcond, null, or, max, apply, mapcar, remove-if-not。remove-if-notで全てremoveされてしまう場合に備え、orを使って空リストのリスト'(())を返すところが今ひとつだがしょうがない。また、補助関数のsublistsというのはたとえば(1 2 3)を((1 2 3) (2 3) (3))のような形、つまり各要素を先頭とするリストのリストに変換するためのもの。これも別の形できれいに書けそうだが今は思いつかない。

(defun lis-length (lst)
  (cond
   ((null lst) 0)                       ;空リストなら0
   (t (1+                               ;サブ問題を解いて、その中の最大値に1を足す
       (apply 'max
              (mapcar
               'lis-length
               (or
                (remove-if-not          ;先頭の数より大きい数から始まるリストだけ抽出
                 (lambda (sublst) (> (car sublst) (car lst)))
                 (sublists (cdr lst)))  ;先頭の数を除いたリスト全て
                '(()))))))))
=> lis-length

(defun sublists (lst)
  (cond
   ((null lst) nil)
   (t (cons lst (sublists (cdr lst))))))
=> sublists

;;; テスト
(sublists '(1 2 3))
=> ((1 2 3) (2 3) (3))

(lis-length nil)
=> 0

(lis-length '(15))
=> 1

(lis-length '(7 15))
=> 2

(lis-length '(11 7 15))
=> 2

(lis-length '(0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15))
=> 6

あとはこの関数にメモ化の機能を追加してやれば、性能が上がって動的計画法で解いたのと同じになる（はず）。

参考

• ALGORITHM NOTE 最長増加部分列 Longest Increasing Subsequence
• Longest increasing subsequence - Wikipedia, the free encyclopedia