Matrix chain multiplication: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|Perl 6}}: Formatting, marked incomplete) |
|||
Line 690: | Line 690: | ||
1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10 |
1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10 |
||
(A1((((((A2A3)A4)(((A5A6)A7)A8))A9)A10)A11)) |
(A1((((((A2A3)A4)(((A5A6)A7)A8))A9)A10)A11)) |
||
</pre> |
|||
=={{header|Phix}}== |
|||
As per the wp pseudocode |
|||
<lang Phix>function optimal_chain_order(int i, int j, sequence s) |
|||
if i==j then |
|||
return i+'A'-1 |
|||
end if |
|||
return "("&optimal_chain_order(i,s[i,j],s) |
|||
&optimal_chain_order(s[i,j]+1,j,s)&")" |
|||
end function |
|||
function optimal_matrix_chain_order(sequence dims) |
|||
integer n = length(dims)-1 |
|||
sequence {m,s} @= repeat(repeat(0,n),n) |
|||
for len=2 to n do |
|||
for i=1 to n-len+1 do |
|||
integer j = i+len-1 |
|||
m[i][j] = -1 |
|||
for k=i to j-1 do |
|||
atom cost := m[i][k] + m[k+1][j] + dims[i]*dims[k+1]*dims[j+1] |
|||
if m[i][j]<0 |
|||
or cost<m[i][j] then |
|||
m[i][j] = cost; |
|||
s[i][j] = k; |
|||
end if |
|||
end for |
|||
end for |
|||
end for |
|||
return {optimal_chain_order(1,n,s),m[1,n]} |
|||
end function |
|||
constant tests = {{5, 6, 3, 1}, |
|||
{1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2}, |
|||
{1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10}} |
|||
for i=1 to length(tests) do |
|||
sequence ti = tests[i] |
|||
printf(1,"Dims : %s\n",{sprint(ti)}) |
|||
printf(1,"Order : %s\nCost : %d\n",optimal_matrix_chain_order(ti)) |
|||
end for</lang> |
|||
{{out}} |
|||
<pre> |
|||
Dims : {5,6,3,1} |
|||
Order : (A(BC)) |
|||
Cost : 48 |
|||
Dims : {1,5,25,30,100,70,2,1,100,250,1,1000,2} |
|||
Order : ((((((((AB)C)D)E)F)G)(H(IJ)))(KL)) |
|||
Cost : 38120 |
|||
Dims : {1000,1,500,12,1,700,2500,3,2,5,14,10} |
|||
Order : (A((((((BC)D)(((EF)G)H))I)J)K)) |
|||
Cost : 1773740 |
|||
</pre> |
</pre> |
||