入れ子のかっこ

Lisp屋には違和感が全くない, 入れ子のかっこの話題だ. TAOCPにかっこの足跡(parenthesis trace)という話がある. (-sesと複数ではなく, -sisと単数なのはなぜか.)
例えば, 左かっこ4個, 右かっこ4個で, 正当なかっこの組み合せを作ると, ()()()(), ()()(()), ..., (((())))の14通りが出来る. n=4で14通りになるというのは, 2009年8月のブログ, 「投票数」に書いた通り.
₈C₄-₈C₃=70-56=14だ.

さて, かっこの足跡は左かっこを0, 右かっこを1で表した二進数である. 従って, ()()()()は01010101, (((())))は00001111となる. この方法で辞書式順で書くと

色の線で囲ったのは, 同じパターンが見えるところだ.

かっこ構造を保ったまま, 辞書式順で次の構造に移るにはどうするか.　二進法の表記では, 右から0と1を数えながら左へ`01'を探す. (0と1の数を#0, #1と書こう.)　ただしこれまで通過した#0<#1でなければならない. そういう`01'を見つけたらそれを`10'と交換し, その右に#0だけ0を並べ, さらにその右に#1だけ1を並べる. これは辞書式順で最小の数を作るためである.

テストするには, 左から探したいので, 左右逆転のリストを使い,

(define x '(1 1 1 1 0 0 0 0))

(define (next x)
 (let ((z 0) (o 0))
  (define (dup n a) (if (= n 0) '() 
   (cons a (dup (- n 1) a))))
  (define (nx x)
   (if x (if (and (= (car x) 1) (= (cadr x) 0) (< z o))
           (append (dup o 1) (dup z 0) '(0 1) (cddr x))
           (begin (if (= (car x) 0) 
              (set! z (+ z 1)) (set! o (+ o 1)))
            (nx (cdr x)))) 'ok))
  (nx x)))

で(set! x (next x))を, x=okになるまで次々と実行する.

実はこれを一気に, 定数ステップで計算するアルゴリズムがあるらしい. これこそプログラムハックである.



μ₀は...010101というパターンの二進数である.

その計算の進行の様子を下に示す.

上の段の左端は説明用の行数である. 左上のxで, 赤い`01'は交換する場所である. 次のozは, それより右の1と0の数. xのビット位置を右から0,1,2,...と数える. #0=#1となる可能性があるのは, 奇数番目の位置にある0なので, 3行目の右端の`01'の0, 8行目の`0101'の0が要注意だ. 奇数番目を取り出すべく, μ₀を利用する.

tはxの右から見て最初の奇数桁目の1の右を0にする. uは反対に最初の奇数桁目の1の左を0に, 右を1にする. つまり右の1は要注意の0を隠す. この1の数は偶数だが, (#0+1)*2であることにも注意. vはuとxの∨でxの交換すべき`01'の右がすべて1になった. 交換すべき`01'の左は現状のまま. これに1を加えれば, `01'が`10'になり, 右は#0+#1個の0になる. 次のv∧¬wは右から#0+#1+1個の1なので, #0+1桁右シフトすれば, 右端に#1個の1が得られる. それが√(u+1)で割る理由である.

すばらしい!