codepad

Language:

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)

Private [?]

Run code