Matrix chain multiplication: Difference between revisions
Content added Content deleted
(+VBA) |
|||
Line 371: | Line 371: | ||
ABCDEFGHIJK -> A × BCDEFGHIJK cost=1773740 |
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> |
</pre> |
||