Anonymous user
Matrix chain multiplication: Difference between revisions
→{{header|Julia}}
(+VBA) |
|||
Line 371:
ABCDEFGHIJK -> A × BCDEFGHIJK cost=1773740
</pre>
=={{header|Haskell}}==
<lang Haskell>
import Data.List
import Data.Char
import Data.Maybe
mats = [[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]]
cost a i j = if (i < j) then
let m = [fst (cost a i k) + fst (cost a (k+1) j) + (a!!i) * (a!!(j+1)) * (a!!(k+1)) | k <- [i..j-1] ] in
let mm = minimum m in (mm, (fromJust $ elemIndex mm m) + i)
else (0, -1)
optimalOrder a i j = if (i < j) then
let c = cost a i j in "(" ++ (optimalOrder a i (snd c)) ++ (optimalOrder a ((snd c) + 1) j) ++ ")"
else [chr((+i) $ ord 'a')]
printBlock v = let c = cost v 0 (length v - 2) in
putStrLn ("for " ++ (show $ v) ++ " we have " ++ (show $ (fst c)) ++ " possibilities, z.B " ++
(optimalOrder v 0 (length v - 2)))
main = mapM_ printBlock mats
</lang>
{{out}}
<pre>
for [5,6,3,1] we have 48 possibilities, z.B (a(bc))
for [1,5,25,30,100,70,2,1,100,250,1,1000,2] we have 38120 possibilities, z.B ((((((((ab)c)d)e)f)g)(h(ij)))(kl))
for [1000,1,500,12,1,700,2500,3,2,5,14,10] we have 1773740 possibilities, z.B (a((((((bc)d)(((ef)g)h))i)j)k))
</pre>
| |||