継子立て

わが家で塵劫記が, それも継子立てが話題になった. 私が小学生の頃持っていた本に塵劫記のことが書いてあり, 私は読んでいたから, 継子立ては70年来のお馴染みである.

Concrete MathematicsやMathWorldによると外国ではJosephusの問題というらしい.

概要はこうだ. 先妻の子15人, 後妻の子15人がいる. 後妻はその中から1人選ぶのを自分の子にしたい.

15人ずつの先妻の子, 後妻の子をある順に円形に並ばせ, 出発の位置から順に数えて10人目ごとに除外する.

次の図の外側の円がそれだ. 円周の内側の黒の数字が位置で, 真上の0から時計回り1,2,...,29まで続く. 円周上の小円内の数字が赤のところには後妻の子を, 黒のところには先妻の子を置く.

小円の中の数字は除外される順を示す. 真上の0から時計廻りに数えると10人目は位置9だ. これが最初なので小円には0を記す. 位置9の子を除外し, その次から数えると10人目は位置19 になる. 小円には1を記し, それも除外し,... を続けると, 小円内の14までが黒なので, (不思議にではないが)先妻の子ばかり14人除外される.



先妻の子の15人目が除外されそうになると, その子は, 次は自分から始めてほしいと訴え, 内側の円のように再開する. 今度は不思議に後妻の子ばかり除外され, 最後に真上の先妻の子0 が残るという話だ.

後妻が子の配置を決めるのは簡単である. 外側のような図を書いてシミュレーションし, 15番目に除外される場所までを先妻の子にすればよい.

しかしコンピュータ屋のわれわれが手でシミュレーションするのは業腹だ. やはりプログラムを書こう.

lispでは円形のリストが作れる.

たとえば

(define foo '(0 1 2 3))
(set-cdr! (list-tail foo 3) foo)

で
位置 0 1 2 3 4 5 6 7 8 9 a b ..
要素(0 1 2 3 0 1 2 3 0 1 2 3 ..)
の無限リストfooができる.

このようにして30人のリストhead (0 1 2 ... 29)を作り, set-cdr!で円形, 無限にする. 10番目, つまり0から数えれば9番目の要素を除外するには

(set-cdr! (list-tail head 8) (list-ref head 10))

で9の両側のリンクが繋がる. これでheadは9の抜けた

(0 1 2 3 4 5 6 7 8 10 11 12 ...)

になる. そうしてheadを9進める.

(set! head (list-tail head 9))

この様子は次の図の左のようだ. headはnextの位置に進む.



しかし円を構成するメンバーの数が少なくなると, これでは失敗する. 上の図の右を見て欲しい. headから0,1,...,と進むと9番はremoveと書いてある1になる. 従ってその両端を繋ぐ. headをnextのところに進めたいが, 9先は0,2,3,4,5,6,7,0,2,3と進んでnext'と書いた3になる.

この失敗をしないためには, 除外する前に10進んでnextの位置を先に確保することだ. そうして書いたプログラムが次だ.

(define (exclude)
(let ((next (list-tail foo 10)))
(set! bar (cons (list-ref foo 9) bar))
(set-cdr! (list-tail foo 8) next)
(set! foo next))
(display bar)
(display (map (lambda (n) (list-ref foo n)) (a2b 0 16))) (newline)
'ok)

後妻も16人の場合をシミュレートすべきであった.