/
matrixChainMultiply.py
43 lines (42 loc) · 1.39 KB
/
matrixChainMultiply.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
''' 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)