Matrix chain multiplication: Difference between revisions
Added FreeBASIC
(→{{header|Haskell}}: Suggested edit (OP may prefer to revert): applied hlint hindent, specified imports) |
(Added FreeBASIC) |
||
(32 intermediate revisions by 18 users not shown) | |||
Line 1:
{{task|Discrete math}}
[[Category:Matrices]]
;Problem
Using the most
For instance, with four matrices, one can compute A(B(CD)), A((BC)D), (AB)(CD), (A(BC))D, (AB)C)D. The number of different ways to put the parens is a [[Catalan numbers|Catalan number]], and grows exponentially with the number of factors.
Line 27 ⟶ 28:
__TOC__
=={{header|11l}}==
{{trans|Nim}}
<syntaxhighlight lang="11l">T Optimizer
[Int] dims
[[Int]] m, s
F (dims)
.dims = dims
F findMatrixChainOrder()
V n = .dims.len - 1
.m = [[0] * n] * n
.s = [[0] * n] * n
L(lg) 1 .< n
L(i) 0 .< n - lg
V j = i + lg
.m[i][j] = 7FFF'FFFF
L(k) i .< j
V cost = .m[i][k] + .m[k + 1][j] + .dims[i] * .dims[k + 1] * .dims[j + 1]
I cost < .m[i][j]
.m[i][j] = cost
.s[i][j] = k
F optimalChainOrder(i, j)
I i == j
R String(Char(code' i + ‘A’.code))
E
R ‘(’(.optimalChainOrder(i, .s[i][j]))‘’
‘’(.optimalChainOrder(.s[i][j] + 1, j))‘)’
V Dims1 = [5, 6, 3, 1]
V Dims2 = [1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]
V Dims3 = [1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]
L(dims) [Dims1, Dims2, Dims3]
V opt = Optimizer(dims)
opt.findMatrixChainOrder()
print(‘Dims: ’dims)
print(‘Order: ’opt.optimalChainOrder(0, dims.len - 2))
print(‘Cost: ’opt.m[0][dims.len - 2])
print(‘’)</syntaxhighlight>
{{out}}
<pre>
Dims: [5, 6, 3, 1]
Order: (A(BC))
Cost: 48
Dims: [1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]
Order: ((((((((AB)C)D)E)F)G)(H(IJ)))(KL))
Cost: 38120
Dims: [1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]
Order: (A((((((BC)D)(((EF)G)H))I)J)K))
Cost: 1773740
</pre>
=={{header|Ada}}==
This example implements the pseudocode in the reference Wiki page. The pseudocode states that the index values for the array to multiply begin at 0 while the cost and order matrices employ index values beginning at 1. Ada supports this pseudocode directly because Ada allows the programmer to define the index range for any array type.
This Ada example is implemented using a simple package and a main procedure. The package specification is:
<syntaxhighlight lang="ada">
package mat_chain is
type Vector is array (Natural range <>) of Integer;
procedure Chain_Multiplication (Dims : Vector);
end mat_chain;
</syntaxhighlight>
The implementation or body of the package is:
<syntaxhighlight lang="ada">
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
package body mat_chain is
type Result_Matrix is
array (Positive range <>, Positive range <>) of Integer;
--------------------------
-- Chain_Multiplication --
--------------------------
procedure Chain_Multiplication (Dims : Vector) is
n : Natural := Dims'Length - 1;
S : Result_Matrix (1 .. n, 1 .. n);
m : Result_Matrix (1 .. n, 1 .. n);
procedure Print (Item : Vector) is
begin
Put ("Array Dimension = (");
for I in Item'Range loop
Put (Item (I)'Image);
if I < Item'Last then
Put (",");
else
Put (")");
end if;
end loop;
New_Line;
end Print;
procedure Chain_Order (Item : Vector) is
J : Natural;
Cost : Natural;
Temp : Natural;
begin
for idx in 1 .. n loop
m (idx, idx) := 0;
end loop;
for Len in 2 .. n loop
for I in 1 .. n - Len + 1 loop
J := I + Len - 1;
m (I, J) := Integer'Last;
for K in I .. J - 1 loop
Temp := Item (I - 1) * Item (K) * Item (J);
Cost := m (I, K) + m (K + 1, J) + Temp;
if Cost < m (I, J) then
m (I, J) := Cost;
S (I, J) := K;
end if;
end loop;
end loop;
end loop;
end Chain_Order;
function Optimal_Parens return String is
function Construct
(S : Result_Matrix; I : Natural; J : Natural)
return Unbounded_String
is
Us : Unbounded_String := Null_Unbounded_String;
Char_Order : Character;
begin
if I = J then
Char_Order := Character'Val (I + 64);
Append (Source => Us, New_Item => Char_Order);
return Us;
else
Append (Source => Us, New_Item => '(');
Append (Source => Us, New_Item => Construct (S, I, S (I, J)));
Append (Source => Us, New_Item => '*');
Append
(Source => Us, New_Item => Construct (S, S (I, J) + 1, J));
Append (Source => Us, New_Item => ')');
return Us;
end if;
end Construct;
begin
return To_String (Construct (S, 1, n));
end Optimal_Parens;
begin
Chain_Order (Dims);
Print (Dims);
Put_Line ("Cost = " & Integer'Image (m (1, n)));
Put_Line ("Optimal Multiply = " & Optimal_Parens);
end Chain_Multiplication;
end mat_chain;
</syntaxhighlight>
The main procedure is:
<syntaxhighlight lang="ada">
with Mat_Chain; use Mat_Chain;
with Ada.Text_IO; use Ada.Text_IO;
procedure chain_main is
V1 : Vector := (5, 6, 3, 1);
V2 : Vector := (1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2);
V3 : Vector := (1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10);
begin
Chain_Multiplication(V1);
New_Line;
Chain_Multiplication(V2);
New_Line;
Chain_Multiplication(V3);
end chain_main;
</syntaxhighlight>
{{output}}
<pre>
Array Dimension = ( 5, 6, 3, 1)
Cost = 48
Optimal Multiply = (A*(B*C))
Array Dimension = ( 1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2)
Cost = 38120
Optimal Multiply = ((((((((A*B)*C)*D)*E)*F)*G)*(H*(I*J)))*(K*L))
Array Dimension = ( 1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10)
Cost = 1773740
Optimal Multiply = (A*((((((B*C)*D)*(((E*F)*G)*H))*I)*J)*K))
</pre>
=={{header|C}}==
{{trans|Kotlin}}
<
#include <limits.h>
#include <stdlib.h>
Line 100 ⟶ 296:
}
return 0;
}</
{{output}}
Line 117 ⟶ 313:
</pre>
=={{header|C sharp|C#}}==
{{trans|Kotlin}}
<
class MatrixChainOrderOptimizer {
Line 178 ⟶ 374:
}
}
}</
{{output}}
Line 193 ⟶ 389:
Order : (A((((((BC)D)(((EF)G)H))I)J)K))
Cost : 1773740
</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <cstdint>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
constexpr int32_t MAXIMUM_VALUE = 2'147'483'647;
std::vector<std::vector<int32_t>> cost;
std::vector<std::vector<int32_t>> order;
void print_vector(const std::vector<int32_t>& list) {
std::cout << "[";
for ( uint64_t i = 0; i < list.size() - 1; ++i ) {
std::cout << list[i] << ", ";
}
std::cout << list.back() << "]" << std::endl;
}
int32_t matrix_chain_order(const std::vector<int32_t>& dimensions) {
const uint64_t size = dimensions.size() - 1;
cost = { size, std::vector<int32_t>(size, 0) };
order = { size, std::vector<int32_t>(size, 0) };
for ( uint64_t m = 1; m < size; ++m ) {
for ( uint64_t i = 0; i < size - m; ++i ) {
int32_t j = i + m;
cost[i][j] = MAXIMUM_VALUE;
for ( int32_t k = i; k < j; ++k ) {
int32_t current_cost = cost[i][k] + cost[k + 1][j]
+ dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
if ( current_cost < cost[i][j] ) {
cost[i][j] = current_cost;
order[i][j] = k;
}
}
}
}
return cost[0][size - 1];
}
std::string get_optimal_parenthesizations(const std::vector<std::vector<int32_t>>& order,
const uint64_t& i, const uint64_t& j) {
if ( i == j ) {
std::string result(1, char(i + 65));
return result;
} else {
std::stringstream stream;
stream << "(" << get_optimal_parenthesizations(order, i, order[i][j])
<< " * " << get_optimal_parenthesizations(order, order[i][j] + 1, j) << ")";
return stream.str();
}
}
void matrix_chain_multiplication(const std::vector<int32_t>& dimensions) {
std::cout << "Array Dimension = "; print_vector(dimensions);
std::cout << "Cost = " << matrix_chain_order(dimensions) << std::endl;
std::cout << "Optimal Multiply = "
<< get_optimal_parenthesizations(order, 0, order.size() - 1) << std::endl << std::endl;
}
int main() {
matrix_chain_multiplication({ 5, 6, 3, 1 });
matrix_chain_multiplication({ 1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2 });
matrix_chain_multiplication({ 1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10 });
}
</syntaxhighlight>
{{ out }}
<pre>
Array Dimension = [5, 6, 3, 1]
Cost = 48
Optimal Multiply = (A * (B * C))
Array Dimension = [1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]
Cost = 38120
Optimal Multiply = ((((((((A * B) * C) * D) * E) * F) * G) * (H * (I * J))) * (K * L))
Array Dimension = [1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]
Cost = 1773740
Optimal Multiply = (A * ((((((B * C) * D) * (((E * F) * G) * H)) * I) * J) * K))
</pre>
=={{header|Fortran}}==
{{trans|Python}}
This is a translation of the Python iterative solution.
<
implicit none
contains
Line 255 ⟶ 534:
call optim([1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2])
call optim([1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10])
end program</
'''Output'''
Line 264 ⟶ 543:
1773740 (1*((((((2*3)*4)*(((5*6)*7)*8))*9)*10)*11))
</pre>
=={{header|FreeBASIC}}==
{{trans|VBA}}
This is a translation of the Python iterative solution.
<syntaxhighlight lang="vbnet">Dim Shared As Integer U(), V()
Sub Aux(i As Integer, j As Integer)
Dim As Integer k = U(i, j)
If k < 0 Then
Print Str(i);
Else
Print "(";
Aux(i, k)
Print "*";
Aux(i + k, j - k)
Print ")";
End If
End Sub
Sub Optimize(a() As Integer)
Dim As Integer i, j, k, c
Dim As Integer n = Ubound(a) - 1
Redim U(n, n), V(n, n)
For i = 1 To n
U(i, 1) = -1
V(i, 1) = 0
Next i
For j = 2 To n
For i = 1 To n - j + 1
V(i, j) = &H7FFFFFFF
For k = 1 To j - 1
c = V(i, k) + V(i + k, j - k) + a(i) * a(i + k) * a(i + j)
If c < V(i, j) Then
U(i, j) = k
V(i, j) = c
End If
Next k
Next i
Next j
Print V(1, n); " ";
Aux(1, n)
Print
Erase U, V
End Sub
Dim As Integer A1(1 To 4) = {5, 6, 3, 1}
Optimize(A1())
Dim As Integer A2(1 To 13) = {1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2}
Optimize(A2())
Dim As Integer A3(1 To 12) = {1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10}
Optimize(A3())
Sleep</syntaxhighlight>
{{out}}
<pre> 48(1*(2*3))
38120((((((((1*2)*3)*4)*5)*6)*7)*(8*(9*10)))*(11*12))
1773740(1*((((((2*3)*4)*(((5*6)*7)*8))*9)*10)*11))</pre>
=={{header|Go}}==
The first <code>for</code> loop is based on the pseudo and Java code from the
[[wp:Matrix_chain_multiplication#A_dynamic_programming_algorithm|Wikipedia article]].
<
import "fmt"
Line 343 ⟶ 681:
fmt.Println()
}
}</
{{out}}
<pre>
Line 374 ⟶ 712:
=={{header|Haskell}}==
<
import Data.Char (chr, ord)
import Data.Maybe (fromJust)
mats :: [[Int]]
Line 392 ⟶ 730:
(a !! i) * (a !! (j + 1)) * (a !! (k + 1))
| k <- [i .. j - 1] ]
| otherwise = (0, -1)
Line 414 ⟶ 752:
main :: IO ()
main = mapM_ printBlock mats</
{{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>
=={{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.
<syntaxhighlight 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
)</syntaxhighlight>
{{out}}
<syntaxhighlight 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))</syntaxhighlight>
=={{header|Java}}==
Thanks to the Wikipedia page for a working Java implementation.
<syntaxhighlight lang="java">
import java.util.Arrays;
public class MatrixChainMultiplication {
public static void main(String[] args) {
runMatrixChainMultiplication(new int[] {5, 6, 3, 1});
runMatrixChainMultiplication(new int[] {1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2});
runMatrixChainMultiplication(new int[] {1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10});
}
private static void runMatrixChainMultiplication(int[] dims) {
System.out.printf("Array Dimension = %s%n", Arrays.toString(dims));
System.out.printf("Cost = %d%n", matrixChainOrder(dims));
System.out.printf("Optimal Multiply = %s%n%n", getOptimalParenthesizations());
}
private static int[][]cost;
private static int[][]order;
public static int matrixChainOrder(int[] dims) {
int n = dims.length - 1;
cost = new int[n][n];
order = new int[n][n];
for (int lenMinusOne = 1 ; lenMinusOne < n ; lenMinusOne++) {
for (int i = 0; i < n - lenMinusOne; i++) {
int j = i + lenMinusOne;
cost[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int currentCost = cost[i][k] + cost[k+1][j] + dims[i]*dims[k+1]*dims[j+1];
if (currentCost < cost[i][j]) {
cost[i][j] = currentCost;
order[i][j] = k;
}
}
}
}
return cost[0][n-1];
}
private static String getOptimalParenthesizations() {
return getOptimalParenthesizations(order, 0, order.length - 1);
}
private static String getOptimalParenthesizations(int[][]s, int i, int j) {
if (i == j) {
return String.format("%c", i+65);
}
else {
StringBuilder sb = new StringBuilder();
sb.append("(");
sb.append(getOptimalParenthesizations(s, i, s[i][j]));
sb.append(" * ");
sb.append(getOptimalParenthesizations(s, s[i][j] + 1, j));
sb.append(")");
return sb.toString();
}
}
}
</syntaxhighlight>
{{out}}
<pre>
Array Dimension = [5, 6, 3, 1]
Cost = 48
Optimal Multiply = (A * (B * C))
Array Dimension = [1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]
Cost = 38120
Optimal Multiply = ((((((((A * B) * C) * D) * E) * F) * G) * (H * (I * J))) * (K * L))
Array Dimension = [1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]
Cost = 1773740
Optimal Multiply = (A * ((((((B * C) * D) * (((E * F) * G) * H)) * I) * J) * K))
</pre>
=={{header|jq}}==
{{trans|Wren}}
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<syntaxhighlight lang="jq"># Input: array of dimensions
# output: {m, s}
def optimalMatrixChainOrder:
. as $dims
| (($dims|length) - 1) as $n
| reduce range(1; $n) as $len ({m: [], s: []};
reduce range(0; $n-$len) as $i (.;
($i + $len) as $j
| .m[$i][$j] = infinite
| reduce range($i; $j) as $k (.;
($dims[$i] * $dims [$k + 1] * $dims[$j + 1]) as $temp
| (.m[$i][$k] + .m[$k + 1][$j] + $temp) as $cost
| if $cost < .m[$i][$j]
then .m[$i][$j] = $cost
| .s[$i][$j] = $k
else .
end ) )) ;
# input: {s}
def printOptimalChainOrder($i; $j):
if $i == $j
then [$i + 65] | implode #=> "A", "B", ...
else "(" +
printOptimalChainOrder($i; .s[$i][$j]) +
printOptimalChainOrder(.s[$i][$j] + 1; $j) + ")"
end;
def 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]
];
dimsList[]
| "Dims : \(.)",
(optimalMatrixChainOrder
| "Order : \(printOptimalChainOrder(0; .s|length - 1))",
"Cost : \(.m[0][.s|length - 1])\n" )</syntaxhighlight>
{{out}}
<pre>
Dims : [5,6,3,1]
Order : (AB)
Cost : 90
Dims : [1,5,25,30,100,70,2,1,100,250,1,1000,2]
Order : ((((((((AB)C)D)E)F)G)(H(IJ)))K)
Cost : 37118
Dims : [1000,1,500,12,1,700,2500,3,2,5,14,10]
Order : (A(((((BC)D)(((EF)G)H))I)J))
Cost : 1777600
</pre>
=={{header|Julia}}==
Line 425 ⟶ 954:
'''Module''':
<
using OffsetArrays
Line 454 ⟶ 983:
end
end # module MatrixChainMultiplications</
'''Main''':
<
println(MatrixChainMultiplications.optim([1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]))</
{{out}}
Line 466 ⟶ 995:
=={{header|Kotlin}}==
This is based on the pseudo-code in the Wikipedia article.
<
lateinit var m: List<IntArray>
Line 515 ⟶ 1,044:
println("\nCost : ${m[0][s.size - 1]}\n")
}
}</
{{out}}
Line 532 ⟶ 1,061:
</pre>
==
<syntaxhighlight 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</syntaxhighlight>
{{out}}
<pre>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
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
{{trans|Fortran}}
<syntaxhighlight lang="mathematica">ClearAll[optim, aux]
optim[a_List] := Module[{u, v, n, c, r, s},
n = Length[a] - 1;
u = ConstantArray[0, {n, n}];
v = ConstantArray[\[Infinity], {n, n}];
u[[All, 1]] = -1;
v[[All, 1]] = 0;
Do[
Do[
Do[
c =
v[[i, k]] + v[[i + k, j - k]] + a[[i]] a[[i + k]] a[[i + j]];
If[c < v[[i, j]],
u[[i, j]] = k;
v[[i, j]] = c;
]
,
{k, 1, j - 1}
]
,
{i, 1, n - j + 1}
]
,
{j, 2, n}
];
r = v[[1, n]];
s = aux[u, 1, n];
{r, s}
]
aux[u_, i_, j_] := Module[{k},
k = u[[i, j]];
If[k < 0,
i
,
Inactive[Times][aux[u, i, k], aux[u, i + k, j - k]]
]
]
{r, s} = optim[{1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2}];
r
s
{r, s} = optim[{1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10}];
r
s</syntaxhighlight>
{{out}}
<pre>38120
(((((((1*2)*3)*4)*5)*6)*7)*(8*(9*10)))*(11*12)
1773740
1*((((((2*3)*4)*(((5*6)*7)*8))*9)*10)*11)</pre>
=={{header|MATLAB}}==
{{trans|Fortran}}
<syntaxhighlight lang="matlab">function [r,s] = optim(a)
n = length(a)-1;
u = zeros(n,n);
Line 563 ⟶ 1,216:
s = sprintf("(%s*%s)",aux(u,i,k),aux(u,i+k,j-k));
end
end</
{{out}}
<
r =
Line 588 ⟶ 1,241:
s =
"(1*((((((2*3)*4)*(((5*6)*7)*8))*9)*10)*11))"</
=={{header|Nim}}==
{{trans|Kotlin}}
<syntaxhighlight lang="nim">import sequtils
type Optimizer = object
dims: seq[int]
m: seq[seq[Natural]]
s: seq[seq[Natural]]
proc initOptimizer(dims: openArray[int]): Optimizer =
## Create an optimizer for the given dimensions.
Optimizer(dims: @dims)
proc findMatrixChainOrder(opt: var Optimizer) =
## Find the best order for matrix chain multiplication.
let n = opt.dims.high
opt.m = newSeqWith(n, newSeq[Natural](n))
opt.s = newSeqWith(n, newSeq[Natural](n))
for lg in 1..<n:
for i in 0..<(n - lg):
let j = i + lg
opt.m[i][j] = Natural.high
for k in i..<j:
let cost = opt.m[i][k] + opt.m[k+1][j] + opt.dims[i] * opt.dims[k+1] * opt.dims[j+1]
if cost < opt.m[i][j]:
opt.m[i][j] = cost
opt.s[i][j] = k
proc optimalChainOrder(opt: Optimizer; i, j: Natural): string =
## Return the optimal chain order as a string.
if i == j:
result.add chr(i + ord('A'))
else:
result.add '('
result.add opt.optimalChainOrder(i, opt.s[i][j])
result.add opt.optimalChainOrder(opt.s[i][j] + 1, j)
result.add ')'
when isMainModule:
const
Dims1 = @[5, 6, 3, 1]
Dims2 = @[1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]
Dims3 = @[1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]
for dims in [Dims1, Dims2, Dims3]:
var opt = initOptimizer(dims)
opt.findMatrixChainOrder()
echo "Dims: ", dims
echo "Order: ", opt.optimalChainOrder(0, dims.len - 2)
echo "Cost: ", opt.m[0][dims.len - 2]
echo ""</syntaxhighlight>
{{out}}
<pre>Dims: @[5, 6, 3, 1]
Order: (A(BC))
Cost: 48
Dims: @[1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]
Order: ((((((((AB)C)D)E)F)G)(H(IJ)))(KL))
Cost: 38120
Dims: @[1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]
Order: (A((((((BC)D)(((EF)G)H))I)J)K))
Cost: 1773740</pre>
=={{header|Perl}}==
{{trans|
<
use feature 'say';
Line 638 ⟶ 1,362:
say matrix_mult_chaining(<1 5 25 30 100 70 2 1 100 250 1 1000 2>);
say matrix_mult_chaining(<1000 1 500 12 1 700 2500 3 2 5 14 10>);</
{{out}}
<pre>38120 ((((((((A1A2)A3)A4)A5)A6)A7)(A8(A9A10)))(A11A12))
1773740 (A1((((((A2A3)A4)(((A5A6)A7)A8))A9)A10)A11))</pre>
=={{header|Phix}}==
As per the wp pseudocode
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">optimal_chain_order</span><span style="color: #0000FF;">(</span><span style="color: #004080;">int</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">int</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">==</span><span style="color: #000000;">j</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'A'</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #008000;">"("</span><span style="color: #0000FF;">&</span><span style="color: #000000;">optimal_chain_order</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">&</span><span style="color: #000000;">optimal_chain_order</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">")"</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">optimal_matrix_chain_order</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">dims</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dims</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">len</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">len</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span> <span style="color: #008080;">to</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">cost</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">dims</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">dims</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">dims</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">0</span>
<span style="color: #008080;">or</span> <span style="color: #000000;">cost</span><span style="color: #0000FF;"><</span><span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cost</span><span style="color: #0000FF;">;</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">optimal_chain_order</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span><span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">30</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">100</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">70</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">100</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">250</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1000</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">500</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">700</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2500</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">14</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Dims : %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Order : %s\nCost : %d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">optimal_matrix_chain_order</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 746 ⟶ 1,422:
</pre>
==
We will solve the task in three steps:
Line 757 ⟶ 1,433:
=== Enumeration of parenthesizations ===
<
def aux(n, k):
if n == 1:
Line 769 ⟶ 1,445:
for v in aux(n - i, k + i):
yield [u, v]
yield from aux(n, 0)</
'''Example''' (in the same order as in the task description)
<
print(u)
Line 780 ⟶ 1,456:
[[0, 1], [2, 3]]
[[0, [1, 2]], 3]
[[[0, 1], 2], 3]</
And here is the optimization step:
<
def cost(k):
if type(k) is int:
Line 800 ⟶ 1,476:
cmin = c
umin = u
return cmin, umin</
=== Recursive cost optimization ===
Line 806 ⟶ 1,482:
The previous function optim1 already used recursion, but only to compute the cost of a given parens configuration, whereas another function (a generator actually) provides these configurations. Here we will do both recursively in the same function, avoiding the computation of configurations altogether.
<
def aux(n, k):
if n == 1:
Line 828 ⟶ 1,504:
return m, p, q, u
s, p, q, u = aux(len(a) - 1, 0)
return s, u</
=== Memoized recursive call ===
Line 834 ⟶ 1,510:
The only difference between optim2 and optim3 is the [[:wp:https://en.wikipedia.org/wiki/Memoization|@memoize]] [https://www.python.org/dev/peps/pep-0318/ decorator]. Yet the algorithm is way faster with this. According to Wikipedia, the complexity falls from O(2^n) to O(n^3). This is confirmed by plotting log(time) vs log(n) for n up to 580 (this needs [https://docs.python.org/3/library/sys.html#sys.setrecursionlimit changing Python's recursion limit]).
<
h = {}
def g(*u):
Line 868 ⟶ 1,544:
return m, p, q, u
s, p, q, u = aux(len(a) - 1, 0)
return s, u</
=== Putting all together ===
<
u = [[1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2],
Line 887 ⟶ 1,563:
t2 = time.clock()
print("%s %10.3f %10d %s" % (f.__name__, 1000 * (t2 - t1), s, u))
print()</
'''Output''' (timings are in milliseconds)
Line 914 ⟶ 1,590:
In the previous solution, memoization is done blindly with a dictionary. However, we need to compute the optimal products for all sublists. A sublist is described by its first index and length (resp. i and j+1 in the following function), hence the set of all sublists can be described by the indices of elements in a triangular array u. We first fill the "solution" (there is no product) for sublists of length 1 (u[0]), then for each successive length we optimize using what when know about smaller sublists. Instead of keeping track of the optimal solutions, the single needed one is computed in the end.
<
global u
n = len(a) - 1
Line 942 ⟶ 1,618:
print(optim4([1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]))
print(optim4([1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]))</
'''Output'''
Line 951 ⟶ 1,627:
</pre>
==
<syntaxhighlight lang="rsplus">aux <- function(i, j, u) {
k <- u[[i, j]]
if (k < 0) {
i
} else {
paste0("(", Recall(i, k, u), "*", Recall(i + k, j - k, u), ")")
}
}
chain.mul <- function(a) {
n <- length(a) - 1
u <- matrix(0, n, n)
v <- matrix(0, n, n)
u[, 1] <- -1
for (j in seq(2, n)) {
for (i in seq(n - j + 1)) {
v[[i, j]] <- Inf
for (k in seq(j - 1)) {
s <- v[[i, k]] + v[[i + k, j - k]] + a[[i]] * a[[i + k]] * a[[i + j]]
if (s < v[[i, j]]) {
u[[i, j]] <- k
v[[i, j]] <- s
}
}
}
}
list(cost = v[[1, n]], solution = aux(1, n, u))
}
chain.mul(c(5, 6, 3, 1))
# $cost
# [1] 48
# $solution
# [1] "(1*(2*3))"
chain.mul(c(1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2))
# $cost
# [1] 38120
# $solution
# [1] "((((((((1*2)*3)*4)*5)*6)*7)*(8*(9*10)))*(11*12))"
chain.mul(c(1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10))
# $cost
# [1] 1773740
# $solution
# [1] "(1*((((((2*3)*4)*(((5*6)*7)*8))*9)*10)*11))"</syntaxhighlight>
=={{header|Racket}}==
'''Memoization'''
<syntaxhighlight lang="racket">#lang racket
(define (memoize f)
(define table (make-hash))
(λ args (hash-ref! table args (thunk (apply f args)))))
(struct $ (cost expl))
(define @ vector-ref)
(define (+: #:combine [combine (thunk* #f)] . xs)
($ (apply + (map $-cost xs)) (apply combine (map $-expl xs))))
(define (min: . xs) (argmin $-cost xs))
(define (compute dims)
(define loop
(memoize
(λ (left right)
(cond
[(= 1 (- right left)) ($ 0 left)]
[else (for/fold ([ans ($ +inf.0 #f)]) ([mid (in-range (add1 left) right)])
(min: ans (+: (loop left mid) (loop mid right)
($ (* (@ dims left) (@ dims mid) (@ dims right)) #f)
#:combine (λ (left-answer right-answer _)
(list left-answer '× right-answer)))))]))))
(loop 0 (sub1 (vector-length dims))))</syntaxhighlight>
'''Main'''
<syntaxhighlight lang="racket">(define-syntax-rule (echo <x> ...)
(begin (printf "~a: ~a\n" (~a (quote <x>) #:min-width 12) <x>) ...))
(define (solve input)
(match-define-values ((list ($ cost explanation)) _ time _) (time-apply compute (list input)))
(echo input time cost explanation)
(newline))
(solve #(1 5 25 30 100 70 2 1 100 250 1 1000 2))
(solve #(1000 1 500 12 1 700 2500 3 2 5 14 10))</syntaxhighlight>
'''Output''' (timings are in milliseconds)
<pre>
input : #(1 5 25 30 100 70 2 1 100 250 1 1000 2)
time : 1
cost : 38120
explanation : ((((((((0 × 1) × 2) × 3) × 4) × 5) × 6) × (7 × (8 × 9))) × (10 × 11))
input : #(1000 1 500 12 1 700 2500 3 2 5 14 10)
time : 0
cost : 1773740
explanation : (0 × ((((((1 × 2) × 3) × (((4 × 5) × 6) × 7)) × 8) × 9) × 10))
</pre>
=={{header|Raku}}==
(formerly Perl 6)
This example is based on Moritz Lenz's code, written for Carl Mäsak's Perl 6 Coding Contest, in 2010. Slightly simplified, it fulfills the Rosetta Code task as well.
<syntaxhighlight lang="raku" line>sub matrix-mult-chaining(@dimensions) {
my @cp;
# @cp has a dual function:
# * the upper triangle of the diagonal matrix stores the cost (c) for
# multiplying matrices $i and $j in @cp[$j][$i], where $j > $i
# * the lower triangle stores the path (p) that was used for the lowest cost
# multiplication to get from $i to $j.
# a matrix never needs to be multiplied with itself, so it has cost 0
@cp[$_][$_] = 0 for @dimensions.keys;
my @path;
my $n = @dimensions.end;
for 1 .. $n -> $chain-length {
for 0 .. $n - $chain-length - 1 -> $start {
my $end = $start + $chain-length;
@cp[$end][$start] = Inf; # until we find a better connection
for $start .. $end - 1 -> $step {
my $new-cost = @cp[$step][$start]
+ @cp[$end][$step + 1]
+ [*] @dimensions[$start, $step+1, $end+1];
if $new-cost < @cp[$end][$start] {
@cp[$end][$start] = $new-cost; # cost
@cp[$start][$end] = $step; # path
}
}
}
}
sub find-path(Int $start, Int $end) {
if $start == $end {
take 'A' ~ ($start + 1);
} else {
take '(';
find-path($start, @cp[$start][$end]);
find-path(@cp[$start][$end] + 1, $end);
take ')';
}
}
return @cp[$n-1][0], gather { find-path(0, $n - 1) }.join;
}
say matrix-mult-chaining(<1 5 25 30 100 70 2 1 100 250 1 1000 2>);
say matrix-mult-chaining(<1000 1 500 12 1 700 2500 3 2 5 14 10>);</syntaxhighlight>
{{out}}
<pre>(38120 ((((((((A1A2)A3)A4)A5)A6)A7)(A8(A9A10)))(A11A12)))
(1773740 (A1((((((A2A3)A4)(((A5A6)A7)A8))A9)A10)A11)))</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">use std::collections::HashMap;
fn main() {
println!("{}\n", mcm_display(vec![5, 6, 3, 1]));
println!(
"{}\n",
mcm_display(vec![1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2])
);
println!(
"{}\n",
mcm_display(vec![1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10])
);
}
fn mcm_display(dims: Vec<i32>) -> String {
let mut costs: HashMap<Vec<i32>, (i32, Vec<usize>)> = HashMap::new();
let mut line = format!("Dims : {:?}\n", dims);
let ans = mcm(dims, &mut costs);
let mut mats = (1..=ans.1.len() + 1)
.map(|x| x.to_string())
.collect::<Vec<String>>();
for i in 0..ans.1.len() {
let mat_taken = mats[ans.1[i]].clone();
mats.remove(ans.1[i]);
mats[ans.1[i]] = "(".to_string() + &mat_taken + "*" + &mats[ans.1[i]] + ")";
}
line += &format!("Order: {}\n", mats[0]);
line += &format!("Cost : {}", ans.0);
line
}
fn mcm(dims: Vec<i32>, costs: &mut HashMap<Vec<i32>, (i32, Vec<usize>)>) -> (i32, Vec<usize>) {
match costs.get(&dims) {
Some(c) => c.clone(),
None => {
let ans = if dims.len() == 3 {
(dims[0] * dims[1] * dims[2], vec![0])
} else {
let mut min_cost = std::i32::MAX;
let mut min_path = Vec::new();
for i in 1..dims.len() - 1 {
let taken = dims[(i - 1)..(i + 2)].to_vec();
let mut rest = dims[..i].to_vec();
rest.extend_from_slice(&dims[(i + 1)..]);
let a1 = mcm(taken, costs);
let a2 = mcm(rest, costs);
if a1.0 + a2.0 < min_cost {
min_cost = a1.0 + a2.0;
min_path = vec![i - 1];
min_path.extend_from_slice(&a2.1);
}
}
(min_cost, min_path)
};
costs.insert(dims, ans.clone());
ans
}
}
}</syntaxhighlight>
{{out}}
<pre>
Dims : [5, 6, 3, 1]
Order: (1*(2*3))
Cost : 48
Dims : [1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]
Order: ((((((((1*2)*3)*4)*5)*6)*7)*(8*(9*10)))*(11*12))
Cost : 38120
Dims : [1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]
Order: (1*((((((2*3)*4)*(((5*6)*7)*8))*9)*10)*11))
Cost : 1773740
</pre>
=={{header|Stata}}==
=== Recursive solution ===
{{trans|Python}}
Line 957 ⟶ 1,871:
Here is the equivalent of optim3 in Python's solution. Memoization is done with an [https://www.stata.com/help.cgi?mf_asarray associative array]. Multiple results are returned in a [https://www.stata.com/help.cgi?m2_struct structure]. The same effect as optim2 can be achieved by removing the asarray machinery.
<
struct ans {
real scalar p,q,s
Line 1,017 ⟶ 1,931:
optim((1,5,25,30,100,70,2,1,100,250,1,1000,2))
optim((1000,1,500,12,1,700,2500,3,2,5,14,10))
end</
'''Output'''
Line 1,031 ⟶ 1,945:
{{trans|Fortran}}
<
function aux(u,i,j) {
k = u[i,j]
Line 1,069 ⟶ 1,983:
optim((1,5,25,30,100,70,2,1,100,250,1,1000,2))
optim((1000,1,500,12,1,700,2500,3,2,5,14,10))
end</
'''Output'''
Line 1,083 ⟶ 1,997:
{{trans|Fortran}}
<
Option Base 1
Dim N As Long, U() As Long, V() As Long
Line 1,130 ⟶ 2,044:
Call Optimize(Array(1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2))
Call Optimize(Array(1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10))
End Sub</
'''Output'''
Line 1,138 ⟶ 2,052:
38120 ((((((((1*2)*3)*4)*5)*6)*7)*(8*(9*10)))*(11*12))
1773740 (1*((((((2*3)*4)*(((5*6)*7)*8))*9)*10)*11))
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="wren">var m = []
var s = []
var optimalMatrixChainOrder = Fn.new { |dims|
var n = dims.count - 1
m = List.filled(n, null)
s = List.filled(n, null)
for (i in 0...n) {
m[i] = List.filled(n, 0)
s[i] = List.filled(n, 0)
}
for (len in 1...n) {
for (i in 0...n-len) {
var j = i + len
m[i][j] = 1/0
for (k in i...j) {
var temp = dims[i] * dims [k + 1] * dims[j + 1]
var cost = m[i][k] + m[k + 1][j] + temp
if (cost < m[i][j]) {
m[i][j] = cost
s[i][j] = k
}
}
}
}
}
var printOptimalChainOrder
printOptimalChainOrder = Fn.new { |i, j|
if (i == j) {
System.write(String.fromByte(i + 65))
} else {
System.write("(")
printOptimalChainOrder.call(i, s[i][j])
printOptimalChainOrder.call(s[i][j] + 1, j)
System.write(")")
}
}
var 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 (dims in dimsList) {
System.print("Dims : %(dims)")
optimalMatrixChainOrder.call(dims)
System.write("Order : ")
printOptimalChainOrder.call(0, s.count - 1)
System.print("\nCost : %(m[0][s.count - 1])\n")
}</syntaxhighlight>
{{out}}
<pre>
Dims : [5, 6, 3, 1]
Order : (A(BC))
Cost : 48
Dims : [1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]
Order : ((((((((AB)C)D)E)F)G)(H(IJ)))(KL))
Cost : 38120
Dims : [1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]
Order : (A((((((BC)D)(((EF)G)H))I)J)K))
Cost : 1773740
</pre>
=={{header|zkl}}==
{{trans|Python}}
<
aux:=fcn(n,k,a){ // (int,int,list) --> (int,int,int,list)
if(n==1){
Line 1,180 ⟶ 2,163:
h[key]=r;
return(r);
}</
<
var letters=["A".."Z"].pump(String);
u.pump(String,
fcn(n){ if(List.isType(n)) String("(",pp(n),")") else letters[n] })
}
fcn prnt(s,u){ "%-9,d %s\n\t-->%s\n".fmt(s,u.toString(*,*),pp(u)).println() }</
<
prnt(s,u);
Line 1,193 ⟶ 2,176:
prnt(s,u);
optim3(T(5,6,3,1)) : prnt(_.xplode());</
{{out}}
<pre>
|