Anonymous user
Matrix chain multiplication: Difference between revisions
Added J implementation
No edit summary |
(Added J implementation) |
||
Line 555:
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>
=={{header|J}}==
This is no more than a mindless transliteration of the Wikipedia Java code (for moo; for pooc, the author found Go to have the clearest expression for transliteration).
Given J's incredible strengths with arrays and matrices, the author is certain there is a much more succinct and idiomatic approach available, but hasn't spent the time understanding how the Wikipedia algorithm works, so hasn't made an attempt at a more native J solution. Others on RC are welcome and invited to do so.
<lang j>moo =: verb define
s =. m =. 0 $~ ,~ n=._1+#y
for_lmo. 1+i.<:n do.
for_i. i. n-lmo do.
j =. i + lmo
m =. _ (<i;j)} m
for_k. i+i.j-i do.
cost =. ((<i;k){m) + ((<(k+1);j){m) + */ y {~ i,(k+1),(j+1)
if. cost < ((<i;j){m) do.
m =. cost (<i;j)} m
s =. k (<i;j)} s
end.
end.
end.
end.
m;s
)
poco =: dyad define
'i j' =. y
if. i=j do.
a. {~ 65 + i NB. 65 = a.i.'A'
else.
k =. x {~ <y NB. y = i,j
'(' , (x poco i,k) , (x poco j ,~ 1+k) , ')'
end.
)
optMM =: verb define
'M S' =. moo y
smoutput 'Cost: ' , ": x: M {~ <0;_1
smoutput 'Order: ', S poco 0 , <:#M
)</lang j>
{{out}}
<lang j> optMM 5 6 3 1
Cost: 48
Order: (A(BC))
optMM 1 5 25 30 100 70 2 1 100 250 1 1000 2
Cost: 38120
Order: ((((((((AB)C)D)E)F)G)(H(IJ)))(KL))
optMM 1000 1 500 12 1 700 2500 3 2 5 14 10
Cost: 1773740
Order: (A((((((BC)D)(((EF)G)H))I)J)K))</lang>
=={{header|Java}}==
| |||