matrix_chain_order.py

importsys

"""
Dynamic Programming
Implementation of Matrix Chain Multiplication
Time Complexity: O(n^3)
Space Complexity: O(n^2)
"""


defmatrix_chain_order(array):
n=len(array)
matrix= [[0forxinrange(n)] forxinrange(n)]
sol= [[0forxinrange(n)] forxinrange(n)]

forchain_lengthinrange(2, n):
forainrange(1, n-chain_length+1):
b=a+chain_length-1

matrix[a][b] =sys.maxsize
forcinrange(a, b):
cost= (
matrix[a][c] +matrix[c+1][b] +array[a-1] *array[c] *array[b]
 )
ifcost<matrix[a][b]:
matrix[a][b] =cost
sol[a][b] =c
returnmatrix, sol


# Print order of matrix with Ai as Matrix
defprint_optiomal_solution(optimal_solution, i, j):
ifi==j:
print("A"+str(i), end=" ")
else:
print("(", end=" ")
print_optiomal_solution(optimal_solution, i, optimal_solution[i][j])
print_optiomal_solution(optimal_solution, optimal_solution[i][j] +1, j)
print(")", end=" ")


defmain():
array= [30, 35, 15, 5, 10, 20, 25]
n=len(array)
# Size of matrix created from above array will be
# 30*35 35*15 15*5 5*10 10*20 20*25
matrix, optimal_solution=matrix_chain_order(array)

print("No. of Operation required: "+str(matrix[1][n-1]))
print_optiomal_solution(optimal_solution, 1, n-1)


if__name__=="__main__":
main()