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が挿入された, 新しい木 のように見る.