2020年11月22日日曜日

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.
と書いてあった.

0 件のコメント: