mex関数

mex関数についてブログに全回書いたのは, もう2年も前だった. その頃, Schemeでの実装も 出来ていたが, なんとなく気に入らなかった.
最近, もう少し気持ちよくしたいと思い, やった書き直したので, ブログに記録して おく. まずinsertion. (ins n t)は, nを, 木tに挿入する関数である.

(define (ins n t)  ;inserts n in a tree t, returns a new tree
  (if (null? t) (list '() (list n n) '())
      (let ((lt (car t)) (l (caadr t)) (r (cadadr t))
            (rt (caddr t)))
  (define (insr t)
    (let ((lt (car t)) (m (caadr t)) (s (cadadr t))
          (rt (caddr t)))
      (if (null? rt)
        (if (= s (- n 1)) (begin (set! l m) lt)
            (begin (set! l n) t))
        (list lt (list m s) (insr rt)))))
  (define (insl t)
    (let ((lt (car t)) (m (caadr t)) (s (cadadr t))
          (rt (caddr t)))
      (if (null? lt)
        (if (= m (+ n 1)) (begin (set! r s) rt)
            (begin (set! r n) t))
        (list (insl lt) (list m s) rt))))
  (cond ((<= l n r) t)
        ((= n (- l 1))
          (if (null? lt) (list lt (list n r) rt)
              (let ((lt (insr lt)))
                (list lt (list l r) rt))))
        ((< n (- l 1)) (list (ins n lt) (list l r) rt))
        ((= n (+ r 1))
          (if (null? rt) (list lt (list l n) rt)
              (let ((rt (insl rt)))
                (list lt (list l r) rt))))
        ((> n (+ r 1)) (list lt (list l r) (ins n rt)))))))

一方, これを使う(mex ms)は次のようだ.

(define (mex ns) (let ((t '()))
 (for-each (lambda (n) (set! t (ins n t))) ns)
  (if (null? t) 0
      (begin (while (not (null? (car t))) (set! t (car t)))
             (if (< 0 (caadr t)) 0 (+ (cadadr t) 1))))))

全回と似たような図だが, 8 4 12 2 6 10 14 7 3 5 1 11 13 15 9 の順に挿入した時の木構造の移り代りの図を示す.

左上の A [8,8] 8 は, 左のAが図の記号, 右の8が今回挿入したn, 中央が(最初は空だった)木にnが挿入された, 新しい木 のように見る.

mex関数

アルゴリズムを読んでいると, mexに出会うことがある. mexとは minimum excludantのことで, 最小の排除されたもの, つまり 引数の集合の最小不在者である. 例えば

(mex '()) => 0
(mex '(1 2)) => 0
(mex '(0 2)) => 1
(mex '(0 1)) => 2

前回のブログ, 無限クイーンで説明したbit stringのある処理系では,

(define (mex ns)
 (if (null? ns) 0
  (let* ((l (+ (apply max ns) 2))
         (abs (make-bit-string l #t)))
   (for-each (lambda (n) (bit-string-clear! bs n)) ns)
   (bit-substring-find-next-set-bit bs 0 l))))

nsが(0 1 1 2 3 5 8 13)の時, (mex ns)では. nsのmaxが13だからlは15. 従って1が15個のbit stringが出来, 最初の(右端の)ビットのビット番号は0, 最後の(左端の) ビット番号は14だ.

#*111111111111111

次に位置0, 1, 1, 2,..., 13のビットをクリアして0にすると

#*101111011010000

になる. そして0から15の範囲で最初の1の位置を探すと4であり,

(mex ns) => 4

上のmex関数はこのように動作するが, bit stringの最初の1を探すような飛道具を 使っていて, 快しとしない向きには, 以下の二進木(二分木)を使うアルゴリズムはどうだろうか.

二進木の節点は, 左部分木, その節点の情報, 右部分木 で構成される. 今の アルゴリズムの場合, その節点の情報は範囲[l, r]で, mexをとる集合nsに l<=k<=r要素があることを示す. 二進木に含まれる節点の範囲には重なりがないだけ ではなく, 隣同士の範囲の間には隙間があるようになっている.

隣同士の範囲の間に新しい要素が現れてその隙間を埋めると, 二つの範囲は合体して 一つの範囲になる.

			     
ns=(12 1 3 3 4 4 5 11 6 6 10 14 15 13 4 7)

として, 二進木の出来かたを下の図に示す.

最初の12が来た時に, 範囲[12,12]が出来る(図の右上.) その右の12は, この時の 入力が12であったことを示す.

次に1が来ると, 1は既にある範囲[12,12]の中でもないし, 両端の続きでもなく離れ ているので, 別の範囲[1,1]を作り, [12,12]の節点の左部分木とする(先程の図の下.)

その次の3は, 新しい範囲[3,3]になって, [12,12]の左の[1,1]の右に繋る.

次の3は[3,3]の範囲にあるから, 何もしない.

4は[3,3]の右に接しているから, 範囲[3,3]が[3,4]になる. しかし, その右部分木 の最も左に5がないので, 合体は生じず, 仕事はここで終わる.

図の1列目が終り, 中央の列の上に戻り, 5が来ると, 範囲[3,4]が[3,5]になる.

11が来ると, [12,12]が[11,12]になり, ここでも合体しない.

更に進んで右の列になり, 14,15,13と来ると, 13は[10,12]の 右を13にし, 右の節点に[14,15]があるのでこの二つが合体して, [10,13]の範囲が出来る.

こうしてnsを全て処理した二進木が右下の図になる.

この二進木を中順序で辿り, 最初に来る節点の範囲[1,1]を見る.

この左が0でなければ, mexは0, 0ならば右プラス1がmexである.

二進木の操作になれていれば, プログラムを書くのは造作ない.

なお, nsが空なら, 木も空で, mexは0である.

P.S. Knuth先生へのメイルでこの実装にも触れたら返事に
It is attractive. I don't recall seeing it before.
と書いてあった.