Matrix chain multiplication: Difference between revisions

Line 374:

=={{header|Haskell}}==

<lang Haskell>import Data.Maybe (fromJust)

import Data.List

import Data.List (elemIndex)

import Data.Char

import Data.Char (chr, ord)

import Data.Maybe

mats = [[~~5, 6, 3, 1~~],

mats :: [[Int]]

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]~~]

[ [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~~

cost :: [Int] -> Int -> Int -> (Int, Int)

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)

~~else (0, -1)~~

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)

| otherwise = (0, -1)

optimalOrder a i j = if (i < ~~j) then~~

optimalOrder :: [Int] -> Int -> Int -> String

optimalOrder a i j

⚫

~~let c = cost a i j~~ in "(" ++ (optimalOrder a i (snd c)) ++ (optimalOrder a ((snd c) + 1) j) ++ ")"

~~else [chr((+~~i~~) $~~ ~~ord~~ ~~'a')]~~

| i < j =

let c = cost a i j

⚫

in "(" ++ optimalOrder a i (snd c) ++ optimalOrder a (snd c + 1) j ++ ")"

| otherwise = [chr ((+ i) $ ord 'a')]

printBlock v = ~~let~~ ~~c = cost v 0~~ (~~length v - 2~~) in

printBlock :: [Int] -> IO ()

printBlock v =

putStrLn ("for " ++ (show $ v) ++ " we have " ++ (show $ (fst c)) ++ " possibilities, z.B " ++

~~(optimalOrder~~ v 0 (length v - 2)))

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~~

main :: IO ()

main = mapM_ printBlock mats</lang>

</lang>

⚫

<pre>for [5,6,3,1] we have 48 possibilities, z.B (a(bc))

<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))

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>

=={{header|Julia}}==