Matrix chain multiplication: Difference between revisions

{{task|Discrete math}}

 

;Problem

 

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.

=={{header|11l}}==

{{trans|Nim}}

[Int] dims

[[Int]] m, s

print(‘Order: ’opt.optimalChainOrder(0, dims.len - 2))

print(‘Cost: ’opt.m[0][dims.len - 2])

 

{{out}}

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:

package mat_chain is

type Vector is array (Natural range <>) of Integer;

procedure Chain_Multiplication (Dims : Vector);

end mat_chain;

The implementation or body of the package is:

with Ada.Text_IO; use Ada.Text_IO;

with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;

 

end mat_chain;

The main procedure is:

with Mat_Chain; use Mat_Chain;

with Ada.Text_IO; use Ada.Text_IO;

Chain_Multiplication(V3);

end chain_main;

{{output}}

<pre>

=={{header|C}}==

{{trans|Kotlin}}

#include <limits.h>

#include <stdlib.h>

}

return 0;

 

{{output}}

=={{header|C sharp|C#}}==

{{trans|Kotlin}}

 

class MatrixChainOrderOptimizer {

}

}

 

{{output}}

Order : (A((((((BC)D)(((EF)G)H))I)J)K))

Cost : 1773740

</pre>

 

=={{header|Fortran}}==

{{trans|Python}}

This is a translation of the Python iterative solution.

 

implicit none

contains

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

 

'''Output'''

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"

fmt.Println()

}

{{out}}

<pre>

 

=={{header|Haskell}}==

import Data.Char (chr, ord)

import Data.Maybe (fromJust)

 

main :: IO ()

{{out}}

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

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.

 

s =. m =. 0 $~ ,~ n=._1+#y

for_lmo. 1+i.<:n do.

smoutput 'Cost: ' , ": x: M {~ <0;_1

smoutput 'Order: ', S poco 0 , <:#M

 

{{out}}

 

Cost: 48

Order: (A(BC))

optMM 1000 1 500 12 1 700 2500 3 2 5 14 10

Cost: 1773740

 

=={{header|Java}}==

Thanks to the Wikipedia page for a working Java implementation.

import java.util.Arrays;

 

 

}

{{out}}

<pre>

'''Works with gojq, the Go implementation of jq'''

 

# output: {m, s}

def optimalMatrixChainOrder:

(optimalMatrixChainOrder

| "Order : \(printOptimalChainOrder(0; .s|length - 1))",

{{out}}

<pre>

Cost : 1777600

</pre>

 

=={{header|Julia}}==

 

'''Module''':

 

using OffsetArrays

end

 

 

'''Main''':

 

{{out}}

=={{header|Kotlin}}==

This is based on the pseudo-code in the Wikipedia article.

 

lateinit var m: List<IntArray>

println("\nCost : ${m[0][s.size - 1]}\n")

}

 

{{out}}

 

=={{header|Lua}}==

local function MatrixChainOrder(dims)

local m = {}

printOptimalChainOrder(s)

print("Cost : "..tostring(m[1][#s]).."\n")

 

{{out}}

=={{header|Mathematica}} / {{header|Wolfram Language}}==

{{trans|Fortran}}

optim[a_List] := Module[{u, v, n, c, r, s},

n = Length[a] - 1;

{r, s} = optim[{1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10}];

r

{{out}}

<pre>38120

1773740

1*((((((2*3)*4)*(((5*6)*7)*8))*9)*10)*11)</pre>

 

=={{header|MATLAB}}==

{{trans|Fortran}}

n = length(a)-1;

u = zeros(n,n);

s = sprintf("(%s*%s)",aux(u,i,k),aux(u,i+k,j-k));

end

 

{{out}}

 

 

r =

s =

 

 

=={{header|Nim}}==

{{trans|Kotlin}}

 

type Optimizer = object

echo "Order: ", opt.optimalChainOrder(0, dims.len - 2)

echo "Cost: ", opt.m[0][dims.len - 2]

 

{{out}}

=={{header|Perl}}==

{{trans|Raku}}

use feature 'say';

 

 

say matrix_mult_chaining(<1 5 25 30 100 70 2 1 100 250 1 1000 2>);

{{out}}

<pre>38120 ((((((((A1A2)A3)A4)A5)A6)A7)(A8(A9A10)))(A11A12))

=={{header|Phix}}==

As per the wp pseudocode

<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: #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>

{{out}}

<pre>

=== Enumeration of parenthesizations ===

 

def aux(n, k):

if n == 1:

for v in aux(n - i, k + i):

yield [u, v]

 

'''Example''' (in the same order as in the task description)

 

print(u)

 

[[0, 1], [2, 3]]

[[0, [1, 2]], 3]

 

And here is the optimization step:

 

def cost(k):

if type(k) is int:

cmin = c

umin = u

 

=== Recursive cost optimization ===

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:

return m, p, q, u

s, p, q, u = aux(len(a) - 1, 0)

 

=== Memoized recursive call ===

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

return m, p, q, u

s, p, q, u = aux(len(a) - 1, 0)

 

=== Putting all together ===

 

 

u = [[1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2],

t2 = time.clock()

print("%s %10.3f %10d %s" % (f.__name__, 1000 * (t2 - t1), s, u))

 

'''Output''' (timings are in milliseconds)

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

 

print(optim4([1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]))

 

'''Output'''

</pre>

 

 

'''Memoization'''

 

 

(define (memoize f)

#:combine (λ (left-answer right-answer _)

(list left-answer '× right-answer)))))]))))

 

'''Main'''

 

(begin (printf "~a: ~a\n" (~a (quote <x>) #:min-width 12) <x>) ...))

 

 

(solve #(1 5 25 30 100 70 2 1 100 250 1 1000 2))

 

'''Output''' (timings are in milliseconds)

(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.

my @cp;

# @cp has a dual function:

 

say matrix-mult-chaining(<1 5 25 30 100 70 2 1 100 250 1 1000 2>);

 

{{out}}

 

=={{header|Rust}}==

 

fn main() {

}

}

{{out}}

<pre>

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

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

 

'''Output'''

{{trans|Fortran}}

 

function aux(u,i,j) {

k = u[i,j]

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

 

'''Output'''

{{trans|Fortran}}

 

Option Base 1

Dim N As Long, U() As Long, V() As Long

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

 

'''Output'''

=={{header|Wren}}==

{{trans|Kotlin}}

var s = []

 

printOptimalChainOrder.call(0, s.count - 1)

System.print("\nCost : %(m[0][s.count - 1])\n")

 

{{out}}

=={{header|zkl}}==

{{trans|Python}}

aux:=fcn(n,k,a){ // (int,int,list) --> (int,int,int,list)

if(n==1){

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

}

prnt(s,u);

 

prnt(s,u);

 

{{out}}

<pre>