This challenge is to compute the most efficient multiplication order for a product of several matrices.
The size of the matrices is specified on a single line of standard input. You should print to standard output a list of integers indicating the order in which to do the multiplications to minimize the total multiplication cost.
5x6 6x12 12x100 100x7
3 2 1
The input line will be a space-separated list of matrix sizes, each of which is the number of rows, followed by an
x, followed by the number of columns. For the example, there are 4 matrices to multiply together (so 3 total multiplications), and since matrix multiplication is associative they can be done in any order.
The output should be the order in which to perform the multiplications to minimize total cost. This should be a space-separated list of integers representing the index of the multiplication to perform next. For N matrices, this list should contain the numbers 1 through N-1, inclusive. For example 1, the output
3 2 1 means you should do the
12x100 * 100x7 multiplication first, then the
6x12 * 12x7 multiplication (the second matrix times the result of the previous step), then finally the resulting
5x6 * 6x7 multiplication.
The matrix multiplications will always be compatible, i.e. the number of columns of a matrix will match the number of rows of the subsequent matrix. Assume the cost of multiplying two matrices
AxB * BxC is
Your code must handle lists of up to 100 matrices, each of dimension up to 999, and do so in a reasonable time.
5x10 10x5 5x15 15x5
1 3 2
3 1 2
22x11 11x78 78x123 123x666 666x35 35x97 97x111 111x20 20x50
2 3 4 5 6 7 8 1
Note: for verification, the best total cost for the three examples is 9114, 750, and 1466344.
Shortest code wins!