Matrix chain multiplication: Difference between revisions
→{{header|Phix}}
Thundergnat (talk | contribs) m (→{{header|Perl 6}}: Formatting, marked incomplete) |
|||
Line 690:
1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10
(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>
| |||