[PYTHON] Optimal solution by combining the longest shiritori

Solve the longest shiritori

Combinatorial optimization (http://qiita.com/SaitoTsutomu/items/bfbf4c185ed7004b5721) makes it easy to solve the longest shiritori.

Formulation

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".

image

We will use $ x_ {ij} \ in \ {0, 1 } $ to indicate whether to draw this line or not.

$ \ mbox {objective} $ $ \ sum_i {\ sum_j {x_ {ij}}} $ Connect as much as possible (0)
$ \ mbox {variables} $ $ x_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ Whether $ kw_i $ is next to $ kw_j $ (1)
$ y_i \ ge 0 ~ \ forall i $ Whether $ kw_i $ starts (2)
$ z_i \ ge 0 ~ \ forall i $ $ kw_i $ order (3)
$ \ mbox {subject to} $ $ \ sum_j {x_ {ij}} = 1 ~ \ forall i $ $ The number from kw_i $ is 1 or less (4)
$ \ sum_j {x_ {ji}} = 1 ~ \ forall i $ $ kw_i $ can be less than 1 (5)
$ \ sum_j {x_ {ij}} \ le \ sum_j {x_ {ji}} + y_i ~ \ forall i $ Constraints on $ y $ (6)
$ z_i \ le z_j + 1- (n + 1) \ times (1-x_ {ij}) ~ \ forall i, j $ Constraints on $ z $ (7) )
$ \ sum_i {y_i} = 1 $ Only one beginning (8)

Solve with Python

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