k4st
-
Python,
pasted
on Apr 15:
|
def matrix_chain_product(*S):
"""Given a sequence, S, of matrices, calculate the minimum number of scalar
operations needed to multiply all of them together."""
from sys import maxint
n = len(S)
r = range(0, n)
# create the matrix with default values of zero
M = [[0 for j in r] for i in r] # solution
# create a list of all of the multiplicands. This is a sort of failure
# function
F = [[len(matrix), len(matrix[0])] for matrix in S]
print "dimensions:", F
print
# fill up the matrix
r.pop(0) # take out the first element of the precomputed range
for b in r:
for i in range(0, n-b): # rows
# column, this shifts one forward each time, representing diagonal
# movement
j = i + b
# default the value to an approximation of infinity
M[i][j] = maxint
# we will go over the cells to the left of M[i][j] and approach it
# until we get to M[i][j-1]
# we will also fo from M[i+1][j] and move all the way down, thus
# this loop checks all values on the current row that precede the
# current cell and all the values in the column below this cell.
for k in range(i,j):
# the cost of multiplying these two matrixes
cost = F[i][0] * F[k][1] * F[k+1][1]
# update the current cost if necessary
M[i][j] = min(M[i][j], M[i][k] + M[k+1][j] + cost)
print_matrix(M)
print "minimum operations:", M[0][n-1]
def print_matrix(M):
"""Print out the rows of a matrix"""
for row in M:
print row
print
A = [[1,2,3],[1,2,3]] # 2x3
B = [[1,2,3,4,5],[1,2,3,4,5],[1,2,3,4,5]] # 3x5
C = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]] # 5x4
D = [[1,2],[1,2],[1,2],[1,2]] # 4x2
matrix_chain_product(A, B, C, D)
|
Output:
|
dimensions: [[2, 3], [3, 5], [5, 4], [4, 2]]
[0, 30, 70, 86]
[0, 0, 60, 84]
[0, 0, 0, 40]
[0, 0, 0, 0]
minimum operations: 86
|
|