今度こそ、最長しりとりのアルゴリズム

ついにトリビアの泉の今週のトリビアの種のコーナーについて
3日も連続で書いてしまっている自分がいる。
それだけ衝撃的だったし、ググッたけど、結構みんな衝撃をうけたみたいですね。


さて、調べていたら、どうやら東京農工大学グループは今回の件を
しっかりと研究会で発表していたみたいですね。
http://www.ipsj.or.jp/sig/mps/open/48th/
参加して実際のアルゴリズムを知りたいところです。

                                      • -



しかし、調べてもそれっぽいアルゴリズムを書いた人がいないし、
おととい書いた程度じゃあくやしいので、自分自身でアルゴリズムを考えました！！


あらかじめ書いておくと、自分は一応情報システムの会社で働いているが、
ほぼ新人でありプログラムはほとんど書けません。（涙）
なので間違っていてもご愛嬌。




＜＜＜＜しばらくうんちく。気に入らなければ飛ばしてちょ＞＞＞＞




さて、最長しりとりで重要なのは単語の最初の文字と最後の文字だけです。
で、テレビの説明では探索木を使っていましたが、
あんなものをやっていたらパソコンでも死ぬほど時間がかかります。
よって効率的に単語を摘出していかなくてはならないのですが、
途中の東京農工大の人たちが考えている際にちらっとメモが写りましたが、
繰り返しをかなり行っておりました。これがみそのはず！！


さて、最初の文字と最後の文字が同じもの結局いつ選んでも変わらないため、
最優先で選出できるようにします。
（これは初期に「りょうり」や「りんり」などが続いたので気が付いた人が多いはず。）


あと、10000台や20000台で「いんぎんびろう」→「うらめい」→
「いんぎんこう」のように続いているのを気がついた人はいるかな？
一部でこれはプログラムの質が悪いのでは？という人がいたけど、
これはまさしく逆で、ここがプログラムのみそではないでしょうか。


つまり、何かを基準に最初の文字が2種類や3種類あるものを繰り返しています。
ではその基準とはなんでしょうか？
頭の文字で分けた際に単語数が最も多いものから選ぶことが、
最長になる可能性が多いはずです。
（だから最も多いものと2番目に多いもので繰り返されているから、
「いんぎんびろう」→「うらめい」→「いんぎんこう」のように続いているのもうなずけます。）


あとは頭の文字で分けた際の単語数が最も多いものということですが、
最後の文字が「ん」であったり次に続かない言葉（頭の文字がもうないもの）を
単語数に入れないようにした方が効果が高いと思われます。


ということで、以下の内容でいかが？
便宜上、単語の先頭の文字を「頭」、終わりの文字を「尻」としてます。

【しりとりを長くつなげるアルゴリズム（案）】
(前置き)
単語を「頭」ごとに分類すること。
そして「頭」の文字ごとに「残単語数」を算出できるようにしておく。
（この際「尻」が「ん」の言葉は「残単語数」に含めない。）


(1)　単語の「頭」と「尻」が同じ文字を摘出する。
(2)　(1)に該当する単語がなければ、「尻」で選べるもののなかから、
　　　「残単語数」の最も多い「頭」の文字を持つ単語を摘出する。
(3)　(1)〜(2)を実施してる際に「残単語数」が0の「頭」が出たら、
　　　その「頭」と同じ「尻」を持つ言葉をすべて削除する。
(4)　(1)〜(3)を繰り返し、最後に「ん」がついたら終了



何気にこれだけでかなり長いしりとりができるのでは?
ちなみに、このアルゴリズムでは最も「残単語数」多い単語を選ぶため、
最も効率的なルートを外してしまう可能性があります。
まあそこいらへんは今回の東京農工大の方々に聞きたいところですね。


で、これを元にプログラムを作ってみたいけど……
おれプログラムって書けないじゃん。（T T）
それ以前にデータ打ち込みに72時間とかやりたくないし。

                                      • -



で、75775単語目で「るすばん」のように「る」で始まって
「ん」で終わる言葉が最後の単語ということがわかりましたが、
結局しりとりにおいて「る」で始まる言葉が最も効果的という、
至極一般的にあたりまえのことがわかります。


なので、しりとりを強くなりたい人は以下のサイトで勉強してね。
「る」の世界
http://www.geocities.co.jp/HeartLand-Suzuran/5537/