しりとりの最長問題~基礎的なやり方で~

制作の経緯

授業のアルゴリズムの問題で、最長経路問題やったからしりとりに応用できないかな？やってみよー

ご指摘を受けvisitをメソッドに変更いたしました。

shiritori.py

import copy
import numpy as np

class Word:
    def __init__(self,number,word):
        self.number=number
        self.word=word

class Shiritori:
    def __init__(self,number):
        self.list=[]
        self.number=number
        self.flwlist=[]
        self.word=0

    def install(self,n,w):
        e=Word(n,w)
        self.list.append(e)
        if not e.word[0] in self.flwlist:
            self.flwlist.append(e.word[0])
        if not e.word[-1] in self.flwlist:
            self.flwlist.append(e.word[-1])

    def connect(self):
        self.word=len(self.flwlist)
        matrix=np.zeros([self.word,self.word],int)
        for i in self.list:
            matrix[self.flwlist.index(i.word[0])][self.flwlist.index(i.word[-1])]+=1
        return matrix

    def longestpath(self,matrix):
        longest=[[]]
        for i in range(self.word):
            if i%5==0:
                print(i)
            path=[i]
-            visit(self,matrix,path,longest)
+            self.visit(matrix,path,longest)
        print(longest)
        for i in range(len(longest[0])-1):
            start=self.flwlist[longest[0][i]]
            end=self.flwlist[longest[0][i+1]]
            check=True
            ans=[]
            for j in range(len(self.list)):
                if check:
                    if self.list[j].word[0]==start and self.list[j].word[-1]==end:
                        if not j in ans:
                            check=False
                            ans.append(self.list[j])
        print(len(ans))
        pass
+        def visit(self,matrix,path,longest):
+            for i in range(self.word):
+               if matrix[path[-1]][i]>0:
+                    newmatrix=np.copy(matrix)
+                    newmatrix[path[-1]][i]-=1
+                    newpath=copy.deepcopy(path)
+                    newpath.append(i)
+                    if len(newpath)>len(longest[0]):
+                        longest[0]=copy.deepcopy(newpath)
+                self.visit(newmatrix,newpath,longest)
+        pass

- def visit(self,matrix,path,longest):
-    for i in range(self.word):
-        if matrix[path[-1]][i]>0:
-            newmatrix=np.copy(matrix)
-            newmatrix[path[-1]][i]-=1
-            newpath=copy.deepcopy(path)
-            newpath.append(i)
-            if len(newpath)>len(longest[0]):
-                longest[0]=copy.deepcopy(newpath)
-            visit(self,newmatrix,newpath,longest)
-    pass
    
g=Shiritori(int(input()))
for i in range(g.number):
    g.install(i,input())
g.longestpath(g.connect())

入力したテキスト

data

93
しょうせい
けいたろう
ゆうき
あぶちゃん
たいせい
こだま
いお
はるき
とし
しょうた
ゆうだい
とも
だいち
たくろう
ずみ
あんま
しょうすけ
たかひろ
けいと
なご
たいが
つっち
しょういん
しおん
ともひろ
せいちゃん
まさひろ
えいき
あきら
きらら
こなつ
みお
こころ
りな
あや
しおり
なつ
なな
まや
ももは
ひより
りな
かりん
もか
ゆうか
さら
あき
そら
もか
くれあ
のりか
ひな
ももこ
ゆら
ななこ
つばさ
きょうすけ
けいご
はっとり
ゆうき
まひろ
おおき
ゆうと
こうたろう
しゅう
こーすけ
そうたろう
ひろむ
ちーず
ゆうたろう
あさひ
こばたく
ゆうた
りょうま
なおと
じゅん
かん
ゆたか
そうた
まみけん
みう
ちひろ
やまと
かなみ
きら
かのん
りん
あんじゆ
えま
あやか
ひよ
りさ
ななみすと

結果

0.0%
13.157894736842104%
26.31578947368421%
39.473684210526315%
52.63157894736842%
65.78947368421052%
78.94736842105263%
92.10526315789474%
[6, 4, 8, 1, 11, 5, 2, 13, 0, 27, 10, 28, 13, 14, 12, 27, 20, 9, 33, 6, 29, 27, 20, 20, 23, 16, 17, 18, 3]
['あんじゆ', 'ゆうた', 'たいせい', 'いお', 'おおき', 'きょうすけ', 'けいと', 'とし', 'しおり', 'りょうま', 'まや', 'やまと', 'とも', 'ももは', 'はっとり', 'りな', 'ななこ', 'こばたく', 'くれあ', 'あさひ', 'ひより', 'りな', 'なな', 'なつ', 'つっち', 'ちーず', 'ずみ', 'みう']

今後の課題

• データ数が多くなる（100を超える）と対応できなくなる
  =>整数計画法の利用が必要になってくるかも