Matrix chain multiplication: Difference between revisions
→{{header|Haskell}}: Suggested edit (OP may prefer to revert): applied hlint hindent, specified imports
(→{{header|Haskell}}: Suggested edit (OP may prefer to revert): applied hlint hindent, specified imports) |
|||
Line 374:
=={{header|Haskell}}==
<lang Haskell>import Data.Maybe (fromJust)
import Data.List (elemIndex)
import Data.Char (chr, ord)
mats
mats =
[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
cost a i j
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▼
| i < j =
let mm = minimum m in (mm, (fromJust $ elemIndex mm m) + i) ▼
let m
▲
(a !! i) * (a !! (j + 1)) * (a !! (k + 1))
| k <- [i .. j - 1] ]
in let mm = minimum m
| otherwise = (0, -1)
optimalOrder
optimalOrder a i j
let c = cost a i j in "(" ++ (optimalOrder a i (snd c)) ++ (optimalOrder a ((snd c) + 1) j) ++ ")"▼
|
let c = cost a i j
▲
| otherwise = [chr ((+ i) $ ord 'a')]
printBlock
printBlock v =
let c
in putStrLn
("for " ++
show v ++
" we have " ++
show (fst c) ++
" possibilities, z.B " ++ optimalOrder v 0 (length v - 2))
main
main = mapM_ printBlock mats</lang>
{{out}}
<pre>for [5,6,3,1] we have 48 possibilities, z.B (a(bc))▼
▲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)
=={{header|Julia}}==
| |||