3
\$\begingroup\$

An assignment at school required me to write a Python program for this task:

In the matrix-chain multiplication problem, we are given a sequence of matrices A(1), A(2), …, A(n). The aim is to compute the product A(1) …, A(n) with the minimum number of scalar multiplications. Thus, we have to find an optimal parenthesization of the matrix product A(1) …, A(n) such that the cost of computing the product is minimized.

Here is my solution to this task:

def matrix_product(p):
    """
    Return m and s.

    m[i][j] is the minimum number of scalar multiplications needed to compute the
    product of matrices A(i), A(i + 1), ..., A(j).

    s[i][j] is the index of the matrix after which the product is split in an
    optimal parenthesization of the matrix product.

    p[0... n] is a list such that matrix A(i) has dimensions p[i - 1] x p[i].
    """
    length = len(p) # len(p) = number of matrices + 1

    # m[i][j] is the minimum number of multiplications needed to compute the
    # product of matrices A(i), A(i+1), ..., A(j)
    # s[i][j] is the matrix after which the product is split in the minimum
    # number of multiplications needed

    m = [[-1]*length for _ in range(length)]
    s = [[-1]*length for _ in range(length)]

    matrix_product_helper(p, 1, length - 1, m, s)

    return m, s


def matrix_product_helper(p, start, end, m, s):

    """
    Return the minimum number of scalar multiplications needed to compute the
    product of matrices A(start), A(start + 1), ..., A(end).

    The minimum number of scalar multiplications needed to compute the
    product of matrices A(i), A(i + 1), ..., A(j) is stored in m[i][j].

    The index of the matrix after which the above product is split in an optimal
    parenthesization is stored in s[i][j].

    p[0... n] is a list such that matrix A(i) has dimensions p[i - 1] x p[i].
    """
    if m[start][end] >= 0:
        return m[start][end]

    if start == end:
        q = 0
    else:
        q = float('inf')
        for k in range(start, end):
            temp = matrix_product_helper(p, start, k, m, s) \
                   + matrix_product_helper(p, k + 1, end, m, s) \
                   + p[start - 1]*p[k]*p[end]
            if q > temp:
                q = temp
                s[start][end] = k

    m[start][end] = q
    return q


def print_parenthesization(s, start, end):
    """
    Print the optimal parenthesization of the matrix product A(start) x
    A(start + 1) x ... x A(end).

    s[i][j] is the index of the matrix after which the product is split in an
    optimal parenthesization of the matrix product.
    """
    if start == end:
        print('A[{}]'.format(start), end='')
        return

    k = s[start][end]

    print('(', end='')
    print_parenthesization(s, start, k)
    print_parenthesization(s, k + 1, end)
    print(')', end='')


n = int(input('Enter number of matrices: '))
p = []
for i in range(n):
    temp = int(input('Enter number of rows in matrix {}: '.format(i + 1)))
    p.append(temp)
temp = int(input('Enter number of columns in matrix {}: '.format(n)))
p.append(temp)

m, s = matrix_product(p)
print('The number of scalar multiplications needed:', m[1][n])
print('Optimal parenthesization: ', end='')
print_parenthesization(s, 1, n)

Here is an example output:

Enter number of matrices: 3
Enter number of rows in matrix 1: 10
Enter number of rows in matrix 2: 100
Enter number of rows in matrix 3: 5
Enter number of columns in matrix 3: 50
The number of scalar multiplications needed: 7500
Optimal parenthesization: ((A[1]A[2])A[3])

Here is the time taken for this output:

0:00:15.332220 seconds.

So, I would like to know whether I could make this program shorter and more efficient.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.