Matrix chain multiplication: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added syntax colouring, made p2js compatible) |
|||
Line 748: | Line 748: | ||
Optimal Multiply = (A * ((((((B * C) * D) * (((E * F) * G) * H)) * I) * J) * K)) |
Optimal Multiply = (A * ((((((B * C) * D) * (((E * F) * G) * H)) * I) * J) * K)) |
||
</pre> |
</pre> |
||
=={{header|jq}}== |
|||
{{trans|Wren}} |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
<lang jq># Input: array of dimensions |
|||
# output: {m, s} |
|||
def optimalMatrixChainOrder: |
|||
. as $dims |
|||
| (($dims|length) - 1) as $n |
|||
| reduce range(1; $n) as $len ({m: [], s: []}; |
|||
reduce range(0; $n-$len) as $i (.; |
|||
($i + $len) as $j |
|||
| .m[$i][$j] = infinite |
|||
| reduce range($i; $j) as $k (.; |
|||
($dims[$i] * $dims [$k + 1] * $dims[$j + 1]) as $temp |
|||
| (.m[$i][$k] + .m[$k + 1][$j] + $temp) as $cost |
|||
| if $cost < .m[$i][$j] |
|||
then .m[$i][$j] = $cost |
|||
| .s[$i][$j] = $k |
|||
else . |
|||
end ) )) ; |
|||
# input: {s} |
|||
def printOptimalChainOrder($i; $j): |
|||
if $i == $j |
|||
then [$i + 65] | implode #=> "A", "B", ... |
|||
else "(" + |
|||
printOptimalChainOrder($i; .s[$i][$j]) + |
|||
printOptimalChainOrder(.s[$i][$j] + 1; $j) + ")" |
|||
end; |
|||
def dimsList: [ |
|||
[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] |
|||
]; |
|||
dimsList[] |
|||
| "Dims : \(.)", |
|||
(optimalMatrixChainOrder |
|||
| "Order : \(printOptimalChainOrder(0; .s|length - 1))", |
|||
"Cost : \(.m[0][.s|length - 1])\n" )</lang> |
|||
{{out}} |
|||
<pre> |
|||
Dims : [5,6,3,1] |
|||
Order : (AB) |
|||
Cost : 90 |
|||
Dims : [1,5,25,30,100,70,2,1,100,250,1,1000,2] |
|||
Order : ((((((((AB)C)D)E)F)G)(H(IJ)))K) |
|||
Cost : 37118 |
|||
Dims : [1000,1,500,12,1,700,2500,3,2,5,14,10] |
|||
Order : (A(((((BC)D)(((EF)G)H))I)J)) |
|||
Cost : 1777600 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |