Optimize matrix chain multiplication

Question

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.

example 1

input

5x6 6x12 12x100 100x7

output

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 A*B*C.

Your code must handle lists of up to 100 matrices, each of dimension up to 999, and do so in a reasonable time.

example 2

input

5x10 10x5 5x15 15x5

output

1 3 2

or

3 1 2

example 3

input

22x11 11x78 78x123 123x666 666x35 35x97 97x111 111x20 20x50

output

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!

Answer 1

Ruby, 176 172 205 characters

Here is another version (several chars longer) which will also run for large input in reasonable time.

q=(gets.split<<$_[/\d+$/]).map &:to_i
r=Hash.new{|h,i|h[i]=Hash.new{|h,j|h[j]=1e12;h[j]=i==j ?[0,[]]:(i...j).map{|k|a,c=r[i][k];b,d=r[k+1][j];[a+b+q[i-1]*q[k]*q[j],c+d+[k]]}.min}}
$><<r[1][q.size-1][1]*' '

First version: straight recursive implementation in Ruby. It does a complete search and thus might be slow on large inputs.

k=->m{m[2]?(1..m.size-2).map{|l|s=k[m[0,l]+m[l+1..-1]];[m[l-1]*m[l]*m[l+1]+s[0],[l]+s[1].map{|u|u<l ?u:u+1}]}.min: [0,[]]}
$><<k[(gets.split<<$_[/\d+$/]).map &:to_i][1]*' '