Algoritmos de Multiplicacao de Matrizes - Cormen

Multiplicacao_De_Matrizes.py

# -*- coding: utf-8 -*-


#len(A) -> Linhas
#len(A[N]) -> Colunas

def MatrixChainOrder(p):
    #m => Custos
    #s => Indice dos Custos
    #p => Comprimentos

    print p
    print 
    infinito = float('inf')
    n = len(p)-1
    m = [[None for x in range(n)] for y in range(n)]
    s = [[None for x in range(n)] for y in range(n)]
    
    for i in range(n):
        m[i][i] = 0

    for l in range(2, n+1):  # l eh o comprimento da cadeia
        for i in range(n - l + 1):
            j = i + l - 1
            m[i][j] = infinito
            for k in range(i, j):
                q = m[i][k] + m[k + 1][j] + (p[i] * p[k+1] * p[j+1])
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k
    return m, s


def PrintOptimalParent(S,i,j):
    if i == j:
        print "A"+str(i),
    else:
        print"(",
        PrintOptimalParent(S, i, S[i][j])
        PrintOptimalParent(S, S[i][j] + 1, j)
        print")",


def MatrixMultiply(A, B):

    AColums = len(A[0])
    ARows = len(A)
    BRows = len(B)
    BColums = len(B[0])

    if AColums != BRows:
        print("Go To Fuck Your Self! huEhuEhuEuHEuh BR")
        return "Comi Sua Mae"
    else:
        C = [[0 for x in range(ARows)] for y in range(BColums)]
        for i in range(ARows):
            for j in range(BColums):
                for k in range(AColums):
                    C[i][j] = C[i][j] + A[i][k] * B[k][j]

        return C


##################
#      MAIN      #
##################

a = [[11, 21, 31],
     [41, 51, 61],
     [71, 81, 91]]

b = [[22, 182, 142],
     [42, 102, 162],
     [62, 122, 182]]

#print MatrixMultiply(a,b)

p = [30, 35, 15, 5, 10, 20, 25]
n = len(p) - 2

M, S = MatrixChainOrder(p)

print "Menor Custo = " + str(M[1][n])
print 
print "Melhor Caminho:"
PrintOptimalParent(S, 0, n)