44 lines
1.4 KiB
Python
44 lines
1.4 KiB
Python
''' mbinary
|
|
#########################################################################
|
|
# File : matrixChainMultiply.py
|
|
# Author: mbinary
|
|
# Mail: zhuheqin1@gmail.com
|
|
# Blog: https://mbinary.xyz
|
|
# Github: https://github.com/mbinary
|
|
# Created Time: 2018-11-05 19:09
|
|
# Description:
|
|
#########################################################################
|
|
'''
|
|
def matrixChainMultiply(seq):
|
|
'''matrix chain multiply, find the optimalest comb to multiply
|
|
eg ABCD, (AB)(CD), A((BC)D)
|
|
seq: sequence of matrix's scale, eg [A.row,A.col,B.col,C.col,D.col]
|
|
'''
|
|
print(seq)
|
|
n = len(seq)-1
|
|
mat = [[0]*n for i in range(n)]
|
|
mark = [[0]*n for i in range(n)]
|
|
for l in range(1,n):
|
|
for i in range(n):
|
|
j = i+l
|
|
if j>=n: continue
|
|
mat[i][j] = None
|
|
for k in range(i,j):
|
|
tmp = mat[i][k]+mat[k+1][j]+seq[i]*seq[k+1]*seq[j+1]
|
|
if mat[i][j] is None or mat[i][j]>tmp:
|
|
mark[i][j] = k
|
|
mat[i][j]= tmp
|
|
s= findSolution(mark,0,n-1)
|
|
print(s)
|
|
return mat[0][n-1]
|
|
def findSolution(mark,i,j):
|
|
if j==i: return 'M{}'.format(i+1)
|
|
if j-i==1: return 'M{} * M{}'.format(j,j+1)
|
|
k = mark[i][j]
|
|
return '('+findSolution(mark,i,k)+') * ('+findSolution(mark,k+1,j)+')'
|
|
|
|
if __name__=='__main__':
|
|
seq = [5,10,3,12,5,50,6]
|
|
res = matrixChainMultiply(seq)
|
|
print(res)
|