Anonymous user
Matrix chain multiplication: Difference between revisions
Added Lua
(Added Lua) |
|||
Line 668:
"(1*((((((2*3)*4)*(((5*6)*7)*8))*9)*10)*11))"</lang>
== {{header|Lua}} ==
<lang lua>-- Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n
local function MatrixChainOrder(dims)
local m = {}
local s = {}
local n = #dims - 1;
-- m[i,j] = Minimum number of scalar multiplications (i.e., cost)
-- needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
-- The cost is zero when multiplying one matrix
for i = 1,n do
m[i] = {}
m[i][i] = 0
s[i] = {}
end
for len = 2,n do -- Subsequence lengths
for i = 1,(n - len + 1) do
local j = i + len - 1
m[i][j] = math.maxinteger
for k = i,(j - 1) do
local cost = m[i][k] + m[k+1][j] + dims[i]*dims[k+1]*dims[j+1];
if (cost < m[i][j]) then
m[i][j] = cost;
s[i][j] = k; --Index of the subsequence split that achieved minimal cost
end
end
end
end
return m,s
end
local function printOptimalChainOrder(s)
local function find_path(start,finish)
local chainOrder = ""
if (start == finish) then
chainOrder = chainOrder .."A"..start
else
chainOrder = chainOrder .."(" ..
find_path(start,s[start][finish]) ..
find_path(s[start][finish]+1,finish) .. ")"
end
return chainOrder
end
print("Order : "..find_path(1,#s))
end
local dimsList = {{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}}
for k,dim in ipairs(dimsList) do
io.write("Dims : [")
for v=1,(#dim-1) do
io.write(dim[v]..", ")
end
print(dim[#dim].."]")
local m,s = MatrixChainOrder(dim)
printOptimalChainOrder(s)
print("Cost : "..tostring(m[1][#s]).."\n")
end</lang>
'''Output'''
<lang lua>Dims : [5, 6, 3, 1]
Order : (A1(A2A3))
Cost : 48
Dims : [1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]
Order : ((((((((A1A2)A3)A4)A5)A6)A7)(A8(A9A10)))(A11A12))
Cost : 38120
Dims : [1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]
Order : (A1((((((A2A3)A4)(((A5A6)A7)A8))A9)A10)A11))
Cost : 1773740
</lang>
=={{header|Perl}}==
{{trans|Perl 6}}
| |||