07/08/05 00:33:49
みんなのお陰で問題解決できたよ。ありがとう。
問題を単純化しようとして敢えて”ボール”と”箱”にしたけれど、本当はバス線の分岐パターンを網羅したいという問題。
バス線につながるノード数と分岐数を決めたとき、全体としてありえる接続パターンを無駄なく網羅したかった。
だから左右対称のパターンは要らないとかの付加条件も発生。
仮にノード数を 8、分岐数を 3 にするとき、バス両端の 2ノード、"分岐"を必ず発生するための 3ノードは固定条件で、
残り 3 ノードをどの各分岐点にいくつ接続するパターンはいくつで、具体的にどうか？という問題になる。
分岐数が変わっても問題を定義できるよう、バス両端のバスを (ノード数 - 2 + 1) 個に分割して考える。この例だと
N03 .N04 .N05 .N06 .N07 N08
.│ .│ │ .│ │ .│
N01─B01┴B02┴B03┴B04┴B05┴B06┴B07─N02
とB01～B07の7本。分岐数を 3 にするということは、B02～B06 のうち 3本の長さをゼロにする処理になる。
長さゼロにすべき3本の組合せパターンを網羅し、そこからランダムに一つ選んで、残りの長さゼロではないバス線と
分岐線による別の処理を・・・というところに行き着ける土台ができますた。
この例のパターンを示すソース
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)