Combinatorial optimization (http://qiita.com/SaitoTsutomu/items/bfbf4c185ed7004b5721) makes it easy to solve the longest shiritori.
It is a variant of the maximum matching problem of the bipartite graph in Typical problem. Let $ kw $ be the word used for shiritori. Arrange $ kw $ on the left and right, with the left as the lead and the right as the trail. And think about drawing a line when connecting. In the figure below, "alignas" is followed by "sizeof".
We will use $ x_ {ij} \ in \ {0, 1 } $ to indicate whether to draw this line or not.
$ \ mbox {objective} $ td> | $ \ sum_i {\ sum_j {x_ {ij}}} $ td> | Connect as much as possible (0) td> tr> |
$ \ mbox {variables} $ td> | $ x_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ td> Whether | $ kw_i $ is next to $ kw_j $ (1) td> tr> |
$ y_i \ ge 0 ~ \ forall i $ td> | Whether $ kw_i $ starts (2) td> tr> | |
$ z_i \ ge 0 ~ \ forall i $ td> | $ kw_i $ order (3) td> tr> | |
$ \ mbox {subject to} $ td> | $ \ sum_j {x_ {ij}} = 1 ~ \ forall i $ td> | $ The number from kw_i $ is 1 or less (4) td> tr> |
$ \ sum_j {x_ {ji}} = 1 ~ \ forall i $ td> | $ kw_i $ can be less than 1 (5) td> tr> | |
$ \ sum_j {x_ {ij}} \ le \ sum_j {x_ {ji}} + y_i ~ \ forall i $ td> | Constraints on $ y $ (6) | |
$ z_i \ le z_j + 1- (n + 1) \ times (1-x_ {ij}) ~ \ forall i, j $ td> | Constraints on $ z $ (7) ) td> tr> | |
$ \ sum_i {y_i} = 1 $ td> | Only one beginning (8) td> tr> |
Let's use 84 C ++ keywords. The keywords are in an array of strings (kw).
python
kw = "alignas,alignof,and,and_eq,asm,auto,bitand,bitor,bool,break,case," \
"catch,char,char16_t,char32_t,class,compl,const,constexpr,const_cast," \
"continue,decltype,default,delete,do,double,dynamic_cast,else,enum," \
"explicit,export,extern,false,float,for,friend,goto,if,inline,int,long," \
"mutable,namespace,new,noexcept,not,not_eq,nullptr,operator,or,or_eq," \
"private,protected,public,register,reinterpret_cast,return,short," \
"signed,sizeof,static,static_assert,static_cast,struct,switch,template," \
"this,thread_local,throw,true,try,typedef,typeid,typename,union," \
"unsigned,using,virtual,void,volatile,wchar_t,while,xor,xor_eq".split(',')
[pulp](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721#%E3%82%BD%E3%83%95%E3%83%88%E3%81%AE%E3%82 Let's formulate and solve using% A4% E3% 83% B3% E3% 82% B9% E3% 83% 88% E3% 83% BC% E3% 83% AB).
python
from pulp import * # pip install pulp
n, r = len(kw), range(len(kw))
m = LpProblem(sense=LpMaximize) #Mathematical model
x = [[0 if kw[i][-1] != kw[j][0] else LpVariable('x%d_%d'%(i,j), cat=LpBinary)
for j in r] for i in r] # kw_i to kw_Whether to connect to j(1)
y = [LpVariable('y%d'%i, lowBound=0) for i in r] # kw_Whether i is the first(2)
z = [LpVariable('z%d'%i, lowBound=0) for i in r] # kw_i's turn(3)
m += lpSum(x[i][j] for i in r for j in r) #Connect as much as possible(0)
for i in r:
cou = lpSum(x[i][j] for j in r) # kw_Number coming out of i
cin = lpSum(x[j][i] for j in r) # kw_Number to enter i
m += cou <= 1 # kw_The number from i is 1 or less(4)
m += cin <= 1 # kw_The number that can enter i is 1 or less(5)
m += cou <= cin + y[i] #Constraints on y(6)
for j in r:
m += z[i] <= z[j]-1+(n+1)*(1-x[i][j]) #Constraints on z(7)
m += lpSum(y) == 1 #Only one at the beginning(8)
%time m.solve() #Solution
print(int(value(m.objective)) + 1) #Maximum number of shiritori
rr = range(1,n+1)
vx = np.vectorize(value)(x).astype(int)
i, s = 0, int(np.vectorize(value)(y)@rr)
while s:
if i:
print(' -> ', end='')
i += 1
print('[%d]%s'%(i,kw[s-1]), end=' ')
s = vx[s-1]@rr
>>>
35
[1]alignas -> [2]signed -> [3]default -> [4]typedef ->
[5]friend -> [6]do -> [7]operator -> [8]reinterpret_cast ->
[9]thread_local -> [10]long -> [11]goto -> [12]or ->
[13]register -> [14]return -> [15]new -> [16]wchar_t ->
[17]true -> [18]export -> [19]throw -> [20]while ->
[21]else -> [22]enum -> [23]mutable -> [24]explicit ->
[25]this -> [26]static -> [27]class -> [28]sizeof ->
[29]float -> [30]template -> [31]extern -> [32]noexcept ->
[33]typeid -> [34]dynamic_cast -> [35]try
If the scale is large, refer to Solving the longest shiritori problem.
2017/1/16 postscript Added variable z to avoid solutions involving loops. If there is a loop, equation (7) will not hold.
reference: I searched for the longest station name Shiritori with Python CodeIQ "Combinatorial optimization: Let's make the longest shiritori from C ++ reserved words!" Sudoku is combined and solved optimally Consider menus by combinatorial optimization I tried to optimize while drying the laundry
Recommended Posts