トポロジカルソート

TAOCPの第1巻にトポロジカルソートのアルゴリズムがある(Algorithm 2.2.3-T). リストの使い方の例である.

例に使う順序には, TAOCPのをそのまま使わせてもらおう. ただ, あの本でのデータは1から始まり, 0は別の機能を持っているが, 私は0から始めるのが好きなので, そういうふうに変更した.

8<1, 2<6, 6<4, 4<7, 7<5, 3<5, 0<2, 6<3, 8<4, 1<7のようなデータがあるとする. 8は1に先行し, 2は6に先行し,...と読む. この関係をグラフにすると, 上の図の上のようになる.

トポロジカルソートはそれを上の図の下のように, 前後関係を保ったまま, 1列に並べるものである.

Algorithm 2.2.3-Tでは, まず要素の個数(上の例では0から8の9個)を受け取り, 下の図のAのようなデータ構造を用意する. 左端の番号は元のデータに出てくる数である.

countはある要素に先行する要素の数を保持する. topはこの要素に後続する要素のリストを保持する. countは最初は0, topは最初はnilである. 8<1を読み込むと, 要素1には先行者8があったので, 1のcountを1増やし, 1を要素8のtopのリストにつなげる. したがってデータ構造はBのようになる.

2<6を読み込むとCになる. 関係をすべて読んだのがDだ.

8<1と8<4を読んだわけだが, 4が1の前にあるのはリスト処理が楽だからで, topのリストの中での順は重要ではない.

count=0の要素0と8は先頭になる資格がある. 従ってソートしたリストに書き出すことが出来る. そしてそれらがソートリストに並んだら, そのtopリストの各要素は邪魔者が1つなくなったので, countを1減らす. その結果0になったら, ソートリストにならぶ権利が得られる. これがトポロジカルソートの基本だ.

TAOCPのアルゴリズムでは, 入力が終わるとcountをしらべ, 権利をもつもののキュー(FIFO)を構成する. count=0になったもののcountの欄を流用する. 以下の図では, キューの関係は赤字で示す. キューを作るには, 先頭(Front)から末尾(Rear)へ至るリストを使う. キューの最後にはnilを入れておく. キューに要素を挿入するのは末尾の側で, 削除するのは先頭の側である. その場所を覚えるためにの変数fとrを用意し, キューが空の時は, f=r=nilとする(E).

要素0のcountが0なので, Fに示すように, 1要素だけのキューが出来, fもrも0を指し, 0のcountがnilになる(F).

さらにcountが0のものを探すと, 要素8が見つかり, Gのようになる. つまりfは0を指し, 0のcountは8になり, 8のcountはnil, rは8となる.

0の探索が終了すると, トポロジカルソートの出力が始まる. その前に変数Nを要素数nにしておき, 出力のたびにNを1減らし, 最後にすべて出力したかをN=0で確認する. まずfの値0を出力, N=N-1とする. 0のtopからリストを辿り, それらに先行していたものがなくなった処理をする. つまり要素2のcountを1減らす. その結果countが0になったら, この要素も先行するものがなくなり, 出力できるようになったわけで, この要素をcountのキューにつなぐ(H). 0のcountは8のままだが, これはゴミである. Algorithm 2.2.3-Tでは, topのリストはそのままにしているが, 演習問題2.2.3-23にあるように, トポロジカルソートが出来なかったときの原因探索用に, 済んだリストはnilにしておくのがよい.

fにfのcountを代入してfを進め, 次の要素の出力に取りかかる. 図Iは要素8も出力したところ, Jは2も出力したところである. キューの先頭をfで辿り出力を続ける. fがnilになったら終わりで, Nは0になったはずである. 0にならなければ, 元のデータがおかしかった(ループがあった)ので, topのリストを出力してみると, 原因がわかる.
,br> 私がSchemeで書いたプログラムは以下のようだ. 変数Nの代わりにnnにしてある.

(define (algorithm223t n ls)
 (let* ((count (make-vector n 0)) (top (make-vector n '()))
        (r '()) (f '()) (nn n))
  (define (getrel ls)   ;データを読み込む 
   (if (not (null? ls))
    (let ((j (caar ls)) (k (cadar ls)))
     (vector-set! count k (+ (vector-ref count k) 1))
     (vector-set! top j (cons k (vector-ref top j)))
     (getrel (cdr ls)))))
  (define (outloop f)   ;出力のループ
   (define (eraserel p) ;topのリストを解消する
    (if (not (null? p))
     (let ((c (- (vector-ref count (car p)) 1)))
      (if (> c 0) (vector-set! count (car p) c)
       (begin (vector-set! count r (car p)) (set! r (car p))
              (vector-set! count r '())))
      (eraserel (cdr p)))
     (begin (vector-set! top f '())
      (outloop (vector-ref count f)))))
   (if (not (null? f))
    (begin (display f) (display " ") (set! nn (- nn 1))
     (eraserel (vector-ref top f)))))
  (getrel ls)
  (do ((k 0 (+ k 1))) ((= k n)) ;count=0のキューを作る
   (if (= (vector-ref count k) 0)
    (begin (if (null? r) (set! f k) (vector-set! count r k))
     (set! r k) (vector-set! count r '()))))
  (outloop f)   ;出力開始
  (if (= nn 0) 'ok (list 'nn nn))))

(algorithm223t 9
'((8 1) (2 6) (6 4) (4 7) (7 5) (3 5) (0 2) (6 3) (8 4) (1 7)))

このプログラムを走らせると 0 8 2 1 6 3 4 7 5 が出力される.

このプログラムに出力命令を追加し, データ入力が終った時のcountとtopの値は #(8 1 1 1 2 2 1 2 ())#((2) (7) (6) (5) (7) () (3 4) (5) (4 1))である.

またデータの最後に(3 0)を追加すると, ループが出来, トポロジカルソートが出来ない. それをやってみると8 1でソートの出力は終り, 残ったtopとして#((2) () (6) (0 5) (7) () (3 4) (5) ())が得られる. これからだとループの発見は面倒だが, 演習問題23のように拡張すると, どこが悪いかが判明する

Life Game

広い空間と長い時間を使えば, Life Gameで計算機がシミュレート出来るという話は聞くが, そう簡単には納得できない.

Winning Waysを読んでいたら, 記憶装置の実現法が書いてあった. こういう方式らしい.

A, B, C, などが記憶場所で, その上方にブロックを置き, そのブロックまでの距離を記憶している値とする. 従って書き込むにはその数値の分だけブロックを遠ざける手続きを繰り返す. また読み出すにはブロックを近づけ, 0になるまでの回数で知る.

近づけたり塔ざけたりには, いつものようにグライダーを使う. 上の図の縦方向は, 実はグライダーの飛ぶ斜め方向である.

ブロックを近づける方法はこうだ.



左上からA, B2機のグライダーがブロックに近づく. この図をクロック0としよう. 目的はブロックを左上へ動かすことである.

その後, クロック10になると, ブロックに衝突したAがブロックを少し移動して下の図になる.



ブロックの元の位置は赤い枠で示したとおりで, 左へ2, 上へ1移動した. 左と上の距離が違うので, もう一度Bをブロックに衝突させる. その結果が次の図だ. (クロック18)



ブロックの位置は, 上へも左へも3移動した.

一方, ブロックを遠ざけるのは簡単ではない.



上の図(クロック0)では, グライダーは左下から右上へ向かっている. 従ってブロックを右上に動かしたい.

グライダーは10機描いてあるが, 2つの編隊になっている. 第1編隊はA, B, C, D, Eで, 最初にブロックに近づくAのミッションは, ブロックに衝突し, 蜂の巣(beehive)4個からなる養蜂場(bee farm)の形にすることだ.

下がクロック24で, Aの衝突の結果, 養蜂場になったところである.



そこへ近づくB, C, Dの3機のミッションは, それぞれ下, 右, 左の蜂の巣と消滅衝突をすることである. 最後のEが近づき, 上に残った蜂の巣に衝突し, ブロックにする.

クロック77になると, 衝突が治まり, ブロックになるが, 赤い枠の元の位置からは左へ1, 上へ２移動した.



すぐ近くに第2編隊のF, G, H, I, Jが接近している. これらは前の編隊とは左下から右上に掛けての45度の線について対称である. Fが養蜂場を作り, G, H, Iが余分の蜂の巣を片付け, 最後にJがブロックに戻す. (164クロック)



これでブロックは右上に(1,1)だけ移動した. しかし先に書いた近づける方は(3,3)だけ移動したので, 遠ざける方は同じことをあと2回やらなければならない. つまり30機をもって押し返すという筋書きである.

ところで, 遠ざける方の最初の図だが, Winning Ways第4巻953ページにある図は, シミュレートしてみると, うまく行かないのである. いろいろテストしてみて, CとEを元の図より1ピクセル下へ, HとJは1ピクセル左へ移動してある. これならうまくいくことがシミュレーションで確認してある.

多面体描画道楽

星形正多面体描画はまだ「大二十面体」が残っていた. (「大二十面体」からは子供の頃読んだ「怪人二十面相」を連想してしまう. でも内容はもう覚えていない.)

一松先生に記述はこうだ「正二十面体の各面に対し, 各辺に隣る三角形の頂点3個を結ぶ正三角形20個を面にとります.」 相変わらず簡潔だ. 面は20, 辺は3×20÷2=30, 頂点は3×20÷5=12. 後に判明するように, 頂点で面は星形(5/2角形)で交わるから, Schläfliの記号は{3,5/2}. いやはや記述とは反対に大変な難物であった.

前回のブログにあった枠になる正二十面体の図をもう一度示すと. つまり頂点0,1,2の面に対しては, それに隣る三角形の頂点5,10,3の三角形で, こういう面だけで出来る立体はそう容易には想像出来ない. 数学者の想像力にはいつもながら脱帽だ. かなりの日時をかけ, 苦心惨憺, 紆余曲折, といいつつも十分楽しんだ末, 出来た図はこれだ. 自画自賛すれば実にもっともらしい. たしかに頂点5,10,3を結ぶ三角形は見える. 下は左が正二十面体の面, 右がそれに対応する大きい三角形である.

[2 1 0]   [10 5 3]
[3 2 0]   [11 1 4]
[4 3 0]   [7 2 5]
[5 4 0]   [8 3 1]
[1 5 0]   [9 4 2]
[2 10 1]  [11 9 0]
[11 10 2] [6 1 3]
[3 11 2]  [7 10 0]
[7 11 3]  [6 2 4]
[4 7 3]   [8 11 0]
[8 7 4]   [6 3 5]
[5 8 4]   [9 7 0]
[9 8 5]   [6 4 1]
[1 9 5]   [10 8 0]
[10 9 1]  [6 5 2]
[7 8 6]   [4 9 11]
[8 9 6]   [5 10 7]
[9 10 6]  [1 11 8]
[10 11 6] [2 7 9]
[11 7 6]  [3 8 10]

ためつすがめつ眺めているうちに, これは下の図のオレンジ色の正五角形の上に, 背の高い星形が乗っている; その正五角形が芯になる正十二面体であるらしいと分かって来た. しかし頂点3に関わる部分だけで三角形は15もある. 都合180個の三角形の座標を計算しなければならぬ. 当然その計算の部分はSchemeで別にやることにした.

星形の底面の凸の点は, 例えばAは頂点3と5の線上にあるから, 後で計算出来るとして, 凹の点Bはどうするか. 頂点3からの三角形の辺は, 8,5,1,10,6に向かい, それらの頂点は8,1,6,5,10の順に星形(5/2角形)につながっている.

ABの線は頂点5, 10の線と平行であり, BCの線は頂点8, 1の線と平行なので, その交点の座標を知る必要がある. このような交点を5個計算し, 3と5の位置を内分してAが得られたように, 3と交点を同じ比で内分するとBが得られるわけだ. この比は1:(1+√5)/2なので, 黄金分割であった.

180個のすべての三角形の頂点の座標が得られてから, それらの各点の視線方向の距離を計算し, 遠い物から順に描くと最初の図が出来た.

一応目的は達成したが, こういう水の溜まる立体を白地で示すと, どこが凸でどこが凹かが分かりにくい. 次は面を濃淡に塗り分けてみたい.

多面体描画道楽

星形正多面体の次の対象は, 「大十二面体」である. 前回は「星形大十二面体」であった. 「大十二面体」と「星形大十二面体」があって, 相並んでいるのは, ノーメンクレイチャとしてはいかがかと思うが, 一松先生の本がそうなので仕方がない. 「星形大十二面体」と「なんとか大十二面体」といいたいところだ. その(星形でない)大十二面体の, 「正多面体を解く」の記述はこうだ. 「正二十面体の頂点に隣る5個の頂点のなす正五角形をそのまま面に採る.」 この上なく簡潔至極の表現だ. 上が正二十面体である. その頂点0に隣る5個の頂点のなす正五角形は, 下の図にオレンジ色で示す面1,2,3,4,5になる.　これを「0に隣る面」ということにしよう. (その辺には小さく0と付記した.) さらに頂点2と3に隣る頂点の面を作ると のように2に隣る面0,1,10,11,3と, 3に隣る面0,2,11,7,4が得られる, ところで0に隣る面と2に隣る面は1と3で交わるからその交線は1から3へ引いた線である. 同様に0に隣る面と3に隣る面は2と4で交わるからその交線は2から4へ引いた線である. さらに2に隣る面と3に隣る面の交線は0から11へ至る. 従ってもとの正二十面体の面の1つの三角形0,2,3の中に3つの交線が現れる. その交点を下の図のようにPとする. 同様に三角形0,3,4の中に3つの交線が現れる. その交点を下の図のようにQとする. この2点の座標が決まると, 大十二面体を描くことが出来る. それがこれだ. この正多面体はPやQの所が凹んでいて, 水が溜まる形である. 右下の頂点3を中心とした昔の陸軍の徽章のような星形がみられる. 3の星の1つの枝は0の星の枝でもあるから, この枝は2等辺三角形である. ところでPやQの座標の計算法だが, 正二十面体をx軸方向から見た図を描くと になる. この図で1, 10短い方の辺の長さを2とすると, 図の 0, 6の長さは1+√5. Oから0までは(1+√5)/2. 0, 3も1なので, これらからP, Qのz座標(3+√5)/2, (√5-1)/2が得られる. これらを解くには (a+b√5)×(c+d√5)のような計算が頻発するから, この積がe+f√5であるとして, a,b,c,dからeとfを求めるプログラム

(define (mult a b c d)
 (list (+ (* a c) (* 5 b d)) (+ (* a d) (* b c))))

を用意すると仕事がはかどった.

多面体描画道楽

一松先生の「正多面体を解く」の星形正多面体に最初に登場するのは, 星形大十二面体である. その記述はこうだ. 「正十二面体の各面の頂点に隣る5個の頂点は同一平面上にあって, 大きな正五角形をなします. これを星形正五角形の形に結びますと, 全体として星形正五角形すなわち正5/2角形が, 各頂点に3個ずつ会する星形正多面体ができます.」

「隣り」を動詞に使うのは数学者だけだが, 意味は十分通じる. そこで描いてみると



正5/2角形を1個描いただけだとこうだが, 12個全部を描くと何も分からない.



この図をプリンタで出力し, 鉛筆であちこちなぞっていると, どうも正五角形の中央を凹ませ, 正十二面体の各頂点を頂点とする三角錐があるように思えてきた.

その凹みの座標を調べるため, 前回のようにzx断面を考えると,  0, 1, 2, 3, 4の面の凹みは3から8の線と4から10の線の交点にあるようだ.



この図で凹みの中心はP, そのz座標は(√5-1)/2である.

ここまで分かると, 後は隠面消去のために面の前後関係の調整だけで, 下のような図が出来た.



この星形正多面体の枠と芯は次のようだ. 外側のオレンジ色の正十二面体が枠で, 内側の紫の正二十面体が芯である. その芯の20個の各面の上に正三角錐が乗っている.

多面体描画道楽

オフィスの近くの神保町. ある日の昼に, 理系の本の多い明倫館書店の前を通り,  そういえば先日購入したのは何だっけ?

その1ヶ月ほど前に, 一松信先生の「正多面体を解く」を買ったのだが紙袋にいれたままオフィスに忘れていた.

この書の最後の方に星形正多面体の話題があった. そういえば以前正多面体や準正多面体をいろいろ描いたが, 星形は手つかずであったので早速その部分を読む.  申し訳ないが一松先生の本の図はどうもいまいち分かりにくいのである. やはりこの際, 自分で描いてみるか.



一松先生の受け売りだが, 2次元の星形正多角形(上の図の左下)の書き方には2通りある.  右上のように「芯」の正多角形の各辺を延長すると左下が出来る. あるいは右下の「枠」となる正多角形の頂点をいくつか置きに結ぶ.

星形正多角形は, 普通の正多角形とは違って見えるが, すべての辺の長さが等しく, すべての頂点の角度も等しいから, やはり正多角形である. この図の星形正多角形は正5/2角形というらしい.

立体の手始めは星形小十二面体である. これは正十二面体を芯とし, その各面を延長する.

2010年6月1日の私のブログの



正十二面体を芯とし, そのプログラムの修正て始めよう.

この正十二面体の正面左上を向いている面(頂点が0, 1, 2, 3, 4の面)に隣接する5枚の面を延長すると点20で合わさった五角錐になり



が出来る. この操作を他の11枚の面についても行うと



が描ける.

五角錐の頂点の座標は下の図のように得られる.



最初の正十二面体で立体を貫くの赤, 緑, 青はx軸, y軸, z軸である. 上の図は立体のzx面の断面である. Aは0と1の, Bは3と13の, Cは8と17の中点で, Oは立体の中心だ.

点20は辺3, 13の延長線上にあり,  立体の辺(稜)の長さの半分を1とすると, OA=OB=OC=(3+√5)/2からx座標が2+√5である.

さて, 星形小十二面体を眺めると, 面0, 1, 2, 3, 4を延長した面28, 21, 29, 26, 24は正5/2角形である. こういう形が12枚あるわけだ. 芯の正十二面体の12の面に五角錐を載せたから, 頂点も12ある. 辺は各頂点から5本出ているが, 相棒の頂点と共有だから都合30本になる.

例のEulerの公式は 面+頂点=辺+2だが, 12+12≠30+2で公式が成り立たないという. 「正多面体を解く」にはちゃんと説明があるが, 受け売りになるので省略.

さてもう1回似たような図を示す.



このオレンジ色の破線は星形正多面体の枠の正二十面体である. 平面だと, 頂点をいくつか置きに辿るといえるが, 立体の場合はどういえばいいだろうか.

一方, 星形小十二面体の隠面消去だが, 五角錐を構成する三角形を遠方にある物から並べ, 各三角形を描画する際, まず内側を白で塗りつぶしてから黒で輪郭を描いた.

始めの正十二面体では, 各面の法線方向を計算し, それと視線の角度を計算して面の見える/見えぬを決めている.

Polyaの問題

彼の名著 How to Solve It に演習問題が20ある. その19番はこうだ.

The side of a regular hexagon is of length n (n is an integer). By equidistant parallels to its sides the hexagon is divided into T equilateral triangles each of which has sides of length 1. Let V denote the number of vertices appearing in this division, and L the number of boundary lines of length 1. (A boundary line belongs to one or two triangles, a vertex to two or more triangles.) When n = 1, which is the simplest case, T = 6, V = 7, L = 12. Consider the general case and express T, V, and L in terms of n. (Guessing is good, proving is better.)


とりあえずn=1,2,3の絵を描いてみる。



こういう図は, 幾何学と同じで正確に描くことが重要である. 幸いPostScriptで奇麗に描けた.

さて, 大きい図で全部数えるのは面倒だし, 間違えの元だ. うまい具合に中の方は赤で囲んだ左隣りと同じだから, 一番外の皮の部分だけに注目する. またそれも6回対称だから, 1/6だけ数えればよい.

n=3の図で数えると, T は5個増えた.　n=2では3増えたから,  ΔT(n)=2n -1であろう. 青い点をつけた頂点V は3増えたから, これはΔV(n)=nだ. Lは8だからΔL(n)=3n -1.

従って1辺がnの時の総和はn=0の時の値に, これらの式の6倍を, nを1からnまでの和にし, 定数はnを掛けて足せばよい.

だから
T(n) = 6·2n(n+1)/2-6n = 6n²+6n-6n = 6n².

V(n) = 6n(n+1)/2+1 = 3n²+3n+1.

L(n)=6·3n(n+1)/2-6n = 9n²+9n-6n = 9n²+3n.


簡単すぎた. 食後の一休みにはちょうどよいかも. PostScriptの絵を描いたり, HTMLで式を書いたりで, 結構時間は掛かったが.