いちばん長いしりとり in diff DouKaku?

いちばん長いしりとり

単語のリストを読み込んで、そのリストにある単語で「しりとり」をします。
一番長くしりとりを続けるためのプログラムを書いてください。
また、単語数に対して、計算量がどのように増えていくかも考えて下さい。

なお、単語リストの一例として
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/index-j.htmlで公開されている
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/fam55_40.txtがあります。

ただし、
・一度使った単語は使わないこと(リストに重複がある可能性は考えなくてよい)
・「ん」で終わる単語を使用するか、リスト内にしりとりを続けられる単語がなくなったときに、しりとりは終了する
・一番最初は、好きな単語から初めてもよい
・「一番長くしりとりを続ける」とは、しりとりが終了するまでに使用する単語数が最大になるよう、しりとりの単語を選ぶことをいう

see: 難聴者のための単語了解度試験用単語リスト

post comment

Posted feedbacks - diff

バグってました orz. 正しくは1秒以内で350語前後でした。

なお、グラフ理論でいうと、任意のグラフから最大の準オイラーグラフとなる部分グラフを抽出するという問題になると思います。

--- Shiritori_old.java  2009-07-27 14:44:42.167161400 +0900
+++ Shiritori_new.java  2009-07-27 14:59:44.602959300 +0900
@@ -46,2 +46,7 @@

+            if(!head.hasCapacity()) {
+                flows.remove(head);
+                break;
+            }
+
             LinkedList<String> path = new LinkedList<String>();
@@ -50,3 +55,3 @@
             while (head.hasCapacity() || tail.hasCapacity()) {
-                if (!head.inEdges.isEmpty()) {
+                if (head.hasCapacity()) {
                     String newHead = popInEdge(head);
@@ -55,5 +60,6 @@
                     head = nodes.get(headChar(newHead));
+                    head.outEdges.remove(newHead);
                 }

-                if (!tail.outEdges.isEmpty()) {
+                if (tail.hasCapacity()) {
                     String newTail = popOutEdge(tail);
@@ -62,2 +68,3 @@
                     tail = nodes.get(tailChar(newTail));
+                    tail.inEdges.remove(newTail);
                 }

DouKaku?

いちばん長いしりとり

Posted feedbacks - diff

Index

Feed

Other

Link

Pathtraq