ぎょーむ日誌 2002-04-12

2002 年 04 月 12 日 (金)

• 0740 起床． やはりもうちょっと早く帰らないと早くに就寝できない． シャワー． 0715 自宅発． 曇． 0730 研究室着． あいかわらずお茶部屋にて朝飯の準備． 朝飯． コーヒー．
• お茶部屋まわりのゴミ捨てと掃除． どうも私がこの部屋をもっともちらかしてるような気がするんで．
• 午前中あれこれ雑事をやったような気がするんだが， 実感としてはまたしても「何もススまなかった」状態． 北大近辺の時間の流れかたは独房区画内とずいぶんと異なる． いまだに慣れない． まぬけだ．
• 甲山さんが査読原稿いらないからあげる， とかいって数式ならんだ紙切れをいただく． 著者は …… おお，Ben Bolker． さらに驚くべきことに， かとー先生もこの人物を知っている． なんでも R-help mailing list の常連投稿者であるから， とのことのようで …… はっかーははっかーを知る， というか．
• お茶部屋で昼飯食おうとしたら， とくに匿名希望する料理人氏が チカ (ワカサギの近縁種らしい) の南蛮づけをタッパーウェアごとめぐんでくれた． ありがたいことです．
• 午後は 平尾君 (D1) と無作為化検定 (の前段階の順列生成) の問題を考えてすごした．
• 無作為化検定 (randomization test) の準備として， ある条件をみたす順列をもれなく・重複なく生成したい． 今回は具体的には {1, 2, 3, ..., 9} という数字を 3 つのグループにわけたい．
• こういうグループ

	{1 2 3} {1 3 2} {2 1 3} {2 3 1} {3 1 2} {3 2 1}

はすべて「同じグループ」とみなす．
• グループ {A, B, C} があったときに (A, B, C はそれぞれ 3 個の数字を含んでいる)

	{A B C} {A C B} {B A C} {B C A} {C A B} {C B A}

はすべて「同じグループ」の組み合わせとみなす．
• …… という条件のもとで可能なグループ・グループ組み合わせを 列挙せよ， という問題だ． あるいは結果の例をみてもらったほうがわかりやすいかもしれない． まず {1 2 3} を

	{1 2 3} {1 3 2} {2 1 3} {2 3 1} {3 1 2} {3 2 1}

…… という「同じ」グループを代表する表記としよう．
• 数字を 1-9 まで使うと 280 通りの組み合わせがあるので， 1-6 の場合を考えると， このとき生成されうるグループは以下の 10 通りとなる．

	{1 2 3} {4 5 6}
	{1 2 4} {3 5 6}
	{1 2 5} {3 4 6}
	{1 2 6} {3 4 5}
	{1 3 4} {2 5 6}
	{1 3 5} {2 4 6}
	{1 3 6} {2 4 5}
	{1 4 5} {2 3 6}
	{1 4 6} {2 3 5}
	{1 5 6} {2 3 4}

• で， われわれが得たかったのは 1-9 つかった場合である．
• 解決に至る道のりをおってみよう． そういうグループ化された順列を生成するプログラムが書きたいわけだ． で， 最初は奥寺アルゴリズム本などまぢめに調べてみた． ところが， こういう「グループ化された順列」とでもいうべきものを生成する ような方法は紹介されていない．
• とはいえ， 順列生成というのはよく使われる技法だから， とりあえず Perl にそういうできあい (かつ高性能な) 順列生成モジュールがないかどうか調べてみた (平尾君も Perl 使い …… Cygwin 上の，ではあるが)． で， やはり CPAN のなかに Algorithm::Permute があった．
• それをダウンロードして make install して， なるほどこういうふうに呼び出すのか， と試運転しているうちに …… ひどく「富豪的」な (すなわち少々おバカな) 方法を思いついた．
• Algorithm::Permute モジュールを呼び出せるコードでは，

	$p = new Algorithm::Permute([1 .. 9])

とすると， 「1 から 9 までのすべての順列」 つまり (1, 2, 3, 4, 5, 6, 7, 8, 9) から (9, 8, 7, 6, 5, 4, 3, 2, 1) までの 9! = 362880 個のリストのリストの参照が $p に代入される． この 362880 とーりの順列のうち 条件に合致する 9! / (3! 3! 3! 3!) = 280 とーりの 順列を選抜すればよろしいのではなかろーか， という贅沢な方法だ．
• で， その選抜方法だけど， じつは上の「1-6 使った実例」に解法のカギの大半は記されてしまっている．
  • {1 2 3} というふうに {小 → 大} と並べるのを 三つ組数字のグループを代表させる記法とする．
  • (1-9 使うんで) 3 つの三つ組数字はすべて {小 → 大} となっていなければならない．
  • 三つ組数字の並べ方は各グループの先頭数字が {小 ○ ○} {中 ○ ○} {大 ○ ○} と並んでいなければならない．
  …… という条件を満たすものとする． 上の 1-6 使った 10 通りの事例は全て上の三条件を充たしている， とわかるだろう．
• 数字 1-9 使った場合の 280 とーりの結果は これ． それを生成する Perl スクリプトは これ． これはコード中の

	my ($group_size, $max) = (3, 9); # Setting #

を書き換えれば， 1-$max の整数を使って $group_size ごとにグループ化した結果が得られる．
• で， 問題は計算に必要となる時間なんだが …… 私の ThinkPad240Z (Celeron 500MHz) では 362880 とーりの順列を生成してそこから 280 個を選抜して ファイルに書き出すのに 19 秒かかった． まぁ， 許容できる「富豪的」アルゴリズムではないでしょーか．
• いかにもすらすらと問題が解決したかのように思われるかもしれないけど， かなり悪戦苦闘して夜までかかってしまった． しかしこれをかとー先生に自慢気に報告すると， (なぜか) ひどくお疲れぎみなのに 「そんなの R でもできますよ」 とあれこれ調べておられる． で， R ではよほどうまく関数を選ばないと 順列生成がすごく遅くなる， とわかった．
• アタマばててるので， 体もばてさせようと北大構内ジョギングに出る． 1840 研究室発で 一昨日と同じようなコースを 40 分ほど走った．
• さらに晩飯食ってみたんだけど …… このあとはお茶部屋雑談で終ってしまった．
• 2130 研究室発． 北 12 生協で買物して 2150 帰宅．
• 今日の食卓
  • 朝 (0850): 米 0.6 合． ナス・タマネギ・ニンジン・シイタケの炒めもの． お茶部屋残留調味料を利用． クレイジーソルト・ウスターソース・サンバル (インドネシアの辛味調味料) など．
  • 昼 (1300): 弁当． 米 0.8 合． 朝の残りととくに匿名希望する料理人氏の チカ 南蛮づけ (かなり美味い)．
  • 晩 (1920): 米 0.6 合． 朝の残り． 南蛮づけ残り …… だけどサカナがすでにないので， 酢につけられたタマネギ・ピーマンのみをかじる．