Posted on by Kalkicode
Code Dynamic Programming

Printing brackets in matrix chain multiplication

Matrix chain multiplication is a common problem in computer science and mathematics that involves finding the most efficient way to multiply a series of matrices. The problem is to determine the optimal order of matrix multiplication, considering that the cost of multiplying two matrices depends on their dimensions. In this article, we will explore the problem statement and provide a solution in Java for printing the brackets in the optimal matrix chain multiplication order.

Problem Statement:

Given a sequence of matrices with their dimensions, the goal is to find the optimal order of matrix multiplication that minimizes the total cost of multiplication. The cost of multiplying two matrices is defined as the number of scalar multiplications required.

For example, given the sequence of matrices A, B, C, and D with dimensions [10x16, 16x12, 12x6, 6x14], we want to find the optimal order of multiplication and print the brackets that represent the order. In this case, the optimal order is ((A(BC))D).

Code Solution

To solve this problem, we can use dynamic programming to find the optimal order of matrix multiplication. We will create two matrices, result and brackets, to store the intermediate results and the optimal brackets respectively.

The result matrix will store the minimum cost of multiplying matrices in the given sequence. The brackets matrix will store the index of the matrix that determines the optimal split at each step.

Here is the step-by-step approach for finding the optimal order and printing the brackets:

  1. Initialize the result and brackets matrices with appropriate dimensions.

  2. Iterate over the matrix chain lengths from 1 to n-1 (n is the number of matrices).

  3. For each chain length, iterate over the matrix chain starting from the first matrix.

  4. Compute the cost of multiplying matrices within the current chain length by considering all possible splits.

  5. Update the result matrix with the minimum cost and record the split index in the brackets matrix.

  6. Finally, use a recursive function showBrackets to print the optimal brackets based on the brackets matrix.

The showBrackets function recursively prints the brackets by splitting the matrices at the recorded indices in the brackets matrix. If the split index is the same for the start and end matrices, it means there is only one matrix, and we print its name. Otherwise, we enclose the matrices within brackets and recursively call the function for the split sections.

// Java Program 
// Printing brackets in matrix chain multiplication
public class Multiplication
{
    public char name;
    public int count;
    public Multiplication()
    {
        this.name = 'A';
        this.count = 0;
    }
    public void showBrackets(int i, int j, int[][] brackets)
    {
        if (i == j)
        {
            if (count != 0)
            {
                System.out.print(name + count);
            }
            else
            {
                System.out.print(name);
            }
            if (name == 'Z')
            {
                // Useful when dimension size is exceed A..Z
                name = 'A';
                count++;
            }
            else
            {
                // Change name
                name++;
            }
        }
        else
        {
            System.out.print("(");
            showBrackets(i, brackets[i][j], brackets);
            showBrackets(brackets[i][j] + 1, j, brackets);
            System.out.print(")");
        }
    }
    public void matrixChainMultiplication(int[] dims, int size)
    {
        int n = size - 1;
        int[][] result = new int[n][n];
        int[][] brackets = new int[n][n];
        int cost = 0;
        int j = 0;
        for (int len = 1; len < n; len++)
        {
            for (int i = 0; i < n - len; i++)
            {
                j = i + len;
                result[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++)
                {
                    cost = result[i][k] + result[k + 1][j] + 
                        dims[i] * dims[k + 1] * dims[j + 1];
                    if (cost < result[i][j])
                    {
                        result[i][j] = cost;
                        brackets[i][j] = k;
                    }
                }
            }
        }
        this.name = 'A';
        this.count = 0;
        // Show Brackets 
        showBrackets(0, n - 1, brackets);
        System.out.print("\n");
    }
    public static void main(String args[])
    {
        Multiplication task = new Multiplication();
        int[] dims1 = {
            10 , 16 , 12 , 6 , 14
        };
        int[] dims2 = {
            8 , 20 , 16 , 10 , 6
        };
        /*
            dims = [10 , 16 , 12 , 6 , 14]
            matri× A = 10 × 16 
            matri× B = 16 × 12
            matri× C = 12 × 6
            matri× D = 6 ×  14
            --------------------
            (A(BC))D

            (16×12×6) + (10×16×6) + (10×6×14)
            =  2952  
        */
        int n = dims1.length;
        task.matrixChainMultiplication(dims1, n);
        n = dims2.length;
        /*
            dims = [8 , 20 , 16 , 10 , 6]
            matri× A = 8 × 20
            matri× B = 20 × 16
            matri× C = 16 × 10
            matri× D = 10 × 6

            A(B(CD)) =  3840

            (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840

        */
        task.matrixChainMultiplication(dims2, n);
    }
}

Output

((A(BC))D)
(A(B(CD)))
// Include header file
#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;
// C++ Program 
// Printing brackets in matrix chain multiplication
class Multiplication
{
    public: char name;
    int count;
    Multiplication()
    {
        this->name = 'A';
        this->count = 0;
    }
    void showBrackets(int i, int j, vector<vector<int>> brackets)
    {
        if (i == j)
        {
            if (this->count != 0)
            {
                cout << this->name + this->count;
            }
            else
            {
                cout << this->name;
            }
            if (this->name == 'Z')
            {
                // Useful when dimension size is exceed A..Z
                this->name = 'A';
                this->count++;
            }
            else
            {
                // Change name
                this->name++;
            }
        }
        else
        {
            cout << "(";
            this->showBrackets(i, brackets[i][j], brackets);
            this->showBrackets(brackets[i][j] + 1, j, brackets);
            cout << ")";
        }
    }
    void matrixChainMultiplication(int dims[], int size)
    {
        int n = size - 1;
        vector<vector<int>> result (n,vector<int>(n,0));
        vector<vector<int>> brackets (n,vector<int>(n,0));
        int cost = 0;
        int j = 0;
        for (int len = 1; len < n; len++)
        {
            for (int i = 0; i < n - len; i++)
            {
                j = i + len;
                result[i][j] = INT_MAX;
                for (int k = i; k < j; k++)
                {
                    cost = result[i][k] + result[k + 1][j] + 
                        dims[i] *dims[k + 1] *dims[j + 1];
                    if (cost < result[i][j])
                    {
                        result[i][j] = cost;
                        brackets[i][j] = k;
                    }
                }
            }
        }
        this->name = 'A';
        this->count = 0;
        // Show Brackets 
        this->showBrackets(0, n - 1, brackets);
        cout << "\n";
    }
};
int main()
{
    Multiplication *task = new Multiplication();
    int dims1[] = {
        10 , 16 , 12 , 6 , 14
    };
    int dims2[] = {
        8 , 20 , 16 , 10 , 6
    };
    /*
        dims = [10 , 16 , 12 , 6 , 14]
        matri× A = 10 × 16 
        matri× B = 16 × 12
        matri× C = 12 × 6
        matri× D = 6 ×  14
        --------------------
        (A(BC))D

        (16×12×6) + (10×16×6) + (10×6×14)
        =  2952  
    */
    int n = sizeof(dims1) / sizeof(dims1[0]);
    task->matrixChainMultiplication(dims1, n);
    n = sizeof(dims2) / sizeof(dims2[0]);
    /*
        dims = [8 , 20 , 16 , 10 , 6]
        matri× A = 8 × 20
        matri× B = 20 × 16
        matri× C = 16 × 10
        matri× D = 10 × 6

        A(B(CD)) =  3840

        (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840

    */
    task->matrixChainMultiplication(dims2, n);
    return 0;
}

Output

((A(BC))D)
(A(B(CD)))
// Include namespace system
using System;
// Csharp Program
// Printing brackets in matrix chain multiplication
public class Multiplication
{
    public char name;
    public int count;
    public Multiplication()
    {
        this.name = 'A';
        this.count = 0;
    }
    public void showBrackets(int i, int j, int[,] brackets)
    {
        if (i == j)
        {
            if (this.count != 0)
            {
                Console.Write(this.name + this.count);
            }
            else
            {
                Console.Write(this.name);
            }
            if (this.name == 'Z')
            {
                // Useful when dimension size is exceed A..Z
                this.name = 'A';
                this.count++;
            }
            else
            {
                // Change name
                this.name++;
            }
        }
        else
        {
            Console.Write("(");
            this.showBrackets(i, brackets[i,j], brackets);
            this.showBrackets(brackets[i,j] + 1, j, brackets);
            Console.Write(")");
        }
    }
    public void matrixChainMultiplication(int[] dims, int size)
    {
        int n = size - 1;
        int[,] result = new int[n,n];
        int[,] brackets = new int[n,n];
        int cost = 0;
        int j = 0;
        for (int len = 1; len < n; len++)
        {
            for (int i = 0; i < n - len; i++)
            {
                j = i + len;
                result[i,j] = int.MaxValue;
                for (int k = i; k < j; k++)
                {
                    cost = result[i,k] + result[k + 1,j] + dims[i] * 
                        dims[k + 1] * dims[j + 1];
                    if (cost < result[i,j])
                    {
                        result[i,j] = cost;
                        brackets[i,j] = k;
                    }
                }
            }
        }
        this.name = 'A';
        this.count = 0;
        // Show Brackets
        this.showBrackets(0, n - 1, brackets);
        Console.Write("\n");
    }
    public static void Main(String[] args)
    {
        Multiplication task = new Multiplication();
        int[] dims1 = {
            10 , 16 , 12 , 6 , 14
        };
        int[] dims2 = {
            8 , 20 , 16 , 10 , 6
        };
        /*
            dims = [10 , 16 , 12 , 6 , 14]
            matri× A = 10 × 16 
            matri× B = 16 × 12
            matri× C = 12 × 6
            matri× D = 6 ×  14
            --------------------
            (A(BC))D
            (16×12×6) + (10×16×6) + (10×6×14)
            =  2952  
        */
        int n = dims1.Length;
        task.matrixChainMultiplication(dims1, n);
        n = dims2.Length;
        /*
            dims = [8 , 20 , 16 , 10 , 6]
            matri× A = 8 × 20
            matri× B = 20 × 16
            matri× C = 16 × 10
            matri× D = 10 × 6
            A(B(CD)) =  3840
            (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
        */
        task.matrixChainMultiplication(dims2, n);
    }
}

Output

((A(BC))D)
(A(B(CD)))
package main
import "math"
import "fmt"
// Go Program
// Printing brackets in matrix chain multiplication
type Multiplication struct {
    name byte
    count int
}
func getMultiplication() * Multiplication {
    var me *Multiplication = &Multiplication {}
    me.name = 'A'
    me.count = 0
    return me
}
func(this *Multiplication) showBrackets(i int, 
    j int, brackets[][] int) {
    if i == j {
        if this.count != 0 {
            fmt.Print(string(this.name), this.count)
        } else {
            fmt.Print(string(this.name))
        }
        if this.name == 'Z' {
            // Useful when dimension size is exceed A..Z
            this.name = 'A'
            this.count++
        } else {
            // Change name
            this.name = this.name + 1
        }
    } else {
        fmt.Print("(")
        this.showBrackets(i, brackets[i][j], brackets)
        this.showBrackets(brackets[i][j] + 1, j, brackets)
        fmt.Print(")")
    }
}
func(this *Multiplication) matrixChainMultiplication(dims[] int, size int) {
    var n int = size - 1
    var result = make([][] int, n)
    for i := 0; i < n; i++ {
        result[i] = make([]int,n)
    }
    var brackets = make([][] int, n)
    for i := 0; i < n; i++ {
        brackets[i] = make([]int,n)
    }
    var cost int = 0
    var j int = 0
    for len := 1 ; len < n ; len++ {
        for i := 0 ; i < n - len ; i++ {
            j = i + len
            result[i][j] = math.MaxInt64
            for k := i ; k < j ; k++ {
                cost = result[i][k] + result[k + 1][j] + dims[i] * 
                dims[k + 1] * dims[j + 1]
                if cost < result[i][j] {
                    result[i][j] = cost
                    brackets[i][j] = k
                }
            }
        }
    }
    this.name = 'A'
    this.count = 0
    // Show Brackets
    this.showBrackets(0, n - 1, brackets)
    fmt.Print("\n")
}
func main() {
    var task * Multiplication = getMultiplication()
    var dims1 = [] int {
        10,
        16,
        12,
        6,
        14,
    }
    var dims2 = [] int {
        8,
        20,
        16,
        10,
        6,
    }
    /*
        dims = [10 , 16 , 12 , 6 , 14]
        matri× A = 10 × 16 
        matri× B = 16 × 12
        matri× C = 12 × 6
        matri× D = 6 ×  14
        --------------------
        (A(BC))D
        (16×12×6) + (10×16×6) + (10×6×14)
        =  2952  
    */
    var n int = len(dims1)
    task.matrixChainMultiplication(dims1, n)
    n = len(dims2)
    /*
        dims = [8 , 20 , 16 , 10 , 6]
        matri× A = 8 × 20
        matri× B = 20 × 16
        matri× C = 16 × 10
        matri× D = 10 × 6
        A(B(CD)) =  3840
        (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    */
    task.matrixChainMultiplication(dims2, n)
}

Output

((A(AB))D)
(A(A(BD)))
<?php
// Php Program
// Printing brackets in matrix chain multiplication
class Multiplication
{
    public $name;
    public $count;
    public	function __construct()
    {
        $this->name = 'A';
        $this->count = 0;
    }
    public	function showBrackets($i, $j, $brackets)
    {
        if ($i == $j)
        {
            if ($this->count != 0)
            {
                echo(ord($this->name) + $this->count);
            }
            else
            {
                echo($this->name);
            }
            if ($this->name == 'Z')
            {
                // Useful when dimension size is exceed A..Z
                $this->name = 'A';
                $this->count++;
            }
            else
            {
                // Change name
                $this->name++;
            }
        }
        else
        {
            echo("(");
            $this->showBrackets($i, $brackets[$i][$j], $brackets);
            $this->showBrackets($brackets[$i][$j] + 1, $j, $brackets);
            echo(")");
        }
    }
    public	function matrixChainMultiplication($dims, $size)
    {
        $n = $size - 1;
        $result = array_fill(0, $n, array_fill(0, $n, 0));
        $brackets = array_fill(0, $n, array_fill(0, $n, 0));
        $cost = 0;
        $j = 0;
        for ($len = 1; $len < $n; $len++)
        {
            for ($i = 0; $i < $n - $len; $i++)
            {
                $j = $i + $len;
                $result[$i][$j] = PHP_INT_MAX;
                for ($k = $i; $k < $j; $k++)
                {
                    $cost = $result[$i][$k] + $result[$k + 1][$j] + $dims[$i] *
                        $dims[$k + 1] * $dims[$j + 1];
                    if ($cost < $result[$i][$j])
                    {
                        $result[$i][$j] = $cost;
                        $brackets[$i][$j] = $k;
                    }
                }
            }
        }
        $this->name = 'A';
        $this->count = 0;
        // Show Brackets
        $this->showBrackets(0, $n - 1, $brackets);
        echo("\n");
    }
}

function main()
{
    $task = new Multiplication();
    $dims1 = array(10, 16, 12, 6, 14);
    $dims2 = array(8, 20, 16, 10, 6);
    /*
        dims = [10 , 16 , 12 , 6 , 14]
        matri× A = 10 × 16 
        matri× B = 16 × 12
        matri× C = 12 × 6
        matri× D = 6 ×  14
        --------------------
        (A(BC))D
        (16×12×6) + (10×16×6) + (10×6×14)
        =  2952  
    */
    $n = count($dims1);
    $task->matrixChainMultiplication($dims1, $n);
    $n = count($dims2);
    /*
        dims = [8 , 20 , 16 , 10 , 6]
        matri× A = 8 × 20
        matri× B = 20 × 16
        matri× C = 16 × 10
        matri× D = 10 × 6
        A(B(CD)) =  3840
        (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    */
    $task->matrixChainMultiplication($dims2, $n);
}
main();

Output

((A(BC))D)
(A(B(CD)))
// Node JS Program
// Printing brackets in matrix chain multiplication
class Multiplication
{
    constructor()
    {
        this.name = 'A';
        this.count = 0;
    }
    showBrackets(i, j, brackets)
    {
        if (i == j)
        {
            if (this.count != 0)
            {
                process.stdout.write("" + this.name.charCodeAt(0) + this.count);
            }
            else
            {
                process.stdout.write(this.name);
            }
            if (this.name == 'Z')
            {
                // Useful when dimension size is exceed A..Z
                this.name = 'A';
                this.count++;
            }
            else
            {
                // Change name
                this.name = String. fromCharCode(this.name.charCodeAt(0) + 
                                                1);
            }
        }
        else
        {
            process.stdout.write("(");
            this.showBrackets(i, brackets[i][j], brackets);
            this.showBrackets(brackets[i][j] + 1, j, brackets);
            process.stdout.write(")");
        }
    }
    matrixChainMultiplication(dims, size)
    {
        var n = size - 1;
        var result = Array(n).fill(0).map(() => new Array(n).fill(0));
        var brackets = Array(n).fill(0).map(() => new Array(n).fill(0));
        var cost = 0;
        var j = 0;
        for (var len = 1; len < n; len++)
        {
            for (var i = 0; i < n - len; i++)
            {
                j = i + len;
                result[i][j] = Number.MAX_VALUE;
                for (var k = i; k < j; k++)
                {
                    cost = result[i][k] + result[k + 1][j] + dims[i] * 
                        dims[k + 1] * dims[j + 1];
                    if (cost < result[i][j])
                    {
                        result[i][j] = cost;
                        brackets[i][j] = k;
                    }
                }
            }
        }
        this.name = 'A';
        this.count = 0;
        // Show Brackets
        this.showBrackets(0, n - 1, brackets);
        process.stdout.write("\n");
    }
}

function main()
{
    var task = new Multiplication();
    var dims1 = [10, 16, 12, 6, 14];
    var dims2 = [8, 20, 16, 10, 6];
    /*
        dims = [10 , 16 , 12 , 6 , 14]
        matri× A = 10 × 16 
        matri× B = 16 × 12
        matri× C = 12 × 6
        matri× D = 6 ×  14
        --------------------
        (A(BC))D
        (16×12×6) + (10×16×6) + (10×6×14)
        =  2952  
    */
    var n = dims1.length;
    task.matrixChainMultiplication(dims1, n);
    n = dims2.length;
    /*
        dims = [8 , 20 , 16 , 10 , 6]
        matri× A = 8 × 20
        matri× B = 20 × 16
        matri× C = 16 × 10
        matri× D = 10 × 6
        A(B(CD)) =  3840
        (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    */
    task.matrixChainMultiplication(dims2, n);
}
main();

Output

((A(BC))D)
(A(B(CD)))
import sys
#  Python 3 Program
#  Printing brackets in matrix chain multiplication
class Multiplication :
    def __init__(self) :
        self.name = 'A'
        self.count = 0
    
    def showBrackets(self, i, j, brackets) :
        if (i == j) :
            if (self.count != 0) :
                print(ord(self.name) + self.count, end = "")
            else :
                print(self.name, end = "")
            
            if (self.name == 'Z') :
                #  Useful when dimension size is exceed A..Z
                self.name = 'A'
                self.count += 1
            else :
                #  Change name
                self.name = chr(ord(self.name) + 1)
            
        else :
            print("(", end = "")
            self.showBrackets(i, brackets[i][j], brackets)
            self.showBrackets(brackets[i][j] + 1, j, brackets)
            print(")", end = "")
        
    
    def matrixChainMultiplication(self, dims, size) :
        n = size - 1
        result = [[0] * (n) for _ in range(n) ]
        brackets = [[0] * (n) for _ in range(n) ]
        cost = 0
        j = 0
        len = 1
        while (len < n) :
            i = 0
            while (i < n - len) :
                j = i + len
                result[i][j] = sys.maxsize
                k = i
                while (k < j) :
                    cost = result[i][k] + result[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                    if (cost < result[i][j]) :
                        result[i][j] = cost
                        brackets[i][j] = k
                    
                    k += 1
                
                i += 1
            
            len += 1
        
        self.name = 'A'
        self.count = 0
        #  Show Brackets
        self.showBrackets(0, n - 1, brackets)
        print(end = "\n")
    

def main() :
    task = Multiplication()
    dims1 = [10, 16, 12, 6, 14]
    dims2 = [8, 20, 16, 10, 6]
    #    dims = [10 , 16 , 12 , 6 , 14]
    #    matri× A = 10 × 16 
    #    matri× B = 16 × 12
    #    matri× C = 12 × 6
    #    matri× D = 6 ×  14
    #    --------------------
    #    (A(BC))D
    #    (16×12×6) + (10×16×6) + (10×6×14)
    #     =  2952  
    n = len(dims1)
    task.matrixChainMultiplication(dims1, n)
    n = len(dims2)
    #    dims = [8 , 20 , 16 , 10 , 6]
    #    matri× A = 8 × 20
    #    matri× B = 20 × 16
    #    matri× C = 16 × 10
    #    matri× D = 10 × 6
    #    A(B(CD)) =  3840
    #    (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    task.matrixChainMultiplication(dims2, n)

if __name__ == "__main__": main()

Output

((A(BC))D)
(A(B(CD)))
#  Ruby Program
#  Printing brackets in matrix chain multiplication
class Multiplication 
    # Define the accessor and reader of class Multiplication
    attr_reader :name, :count
    attr_accessor :name, :count
    def initialize() 
        self.name = 'A'
        self.count = 0
    end

    def showBrackets(i, j, brackets) 
        if (i == j) 
            if (self.count != 0) 
                print(self.name.ord + self.count)
            else

                print(self.name)
            end

            if (self.name == 'Z') 
                #  Useful when dimension size is exceed A..Z
                self.name = 'A'
                self.count += 1
            else

                #  Change name
                self.name = (self.name.ord+1).chr
            end

        else

            print("(")
            self.showBrackets(i, brackets[i][j], brackets)
            self.showBrackets(brackets[i][j] + 1, j, brackets)
            print(")")
        end

    end

    def matrixChainMultiplication(dims, size) 
        n = size - 1
        result = Array.new(n) {Array.new(n) {0}}
        brackets = Array.new(n) {Array.new(n) {0}}
        cost = 0
        j = 0
        len = 1
        while (len < n) 
            i = 0
            while (i < n - len) 
                j = i + len
                result[i][j] = (2 ** (0. size * 8 - 2))
                k = i
                while (k < j) 
                    cost = result[i][k] + result[k + 1][j] + dims[i] *
                        dims[k + 1] * dims[j + 1]
                    if (cost < result[i][j]) 
                        result[i][j] = cost
                        brackets[i][j] = k
                    end

                    k += 1
                end

                i += 1
            end

            len += 1
        end

        self.name = 'A'
        self.count = 0
        #  Show Brackets
        self.showBrackets(0, n - 1, brackets)
        print("\n")
    end

end

def main() 
    task = Multiplication.new()
    dims1 = [10, 16, 12, 6, 14]
    dims2 = [8, 20, 16, 10, 6]
    #    dims = [10 , 16 , 12 , 6 , 14]
    #    matri× A = 10 × 16 
    #    matri× B = 16 × 12
    #    matri× C = 12 × 6
    #    matri× D = 6 ×  14
    #    --------------------
    #    (A(BC))D
    #    (16×12×6) + (10×16×6) + (10×6×14)
    #     =  2952  
    n = dims1.length
    task.matrixChainMultiplication(dims1, n)
    n = dims2.length
    #    dims = [8 , 20 , 16 , 10 , 6]
    #    matri× A = 8 × 20
    #    matri× B = 20 × 16
    #    matri× C = 16 × 10
    #    matri× D = 10 × 6
    #    A(B(CD)) =  3840
    #    (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    task.matrixChainMultiplication(dims2, n)
end

main()

Output

((A(BC))D)
(A(B(CD)))
// Scala Program
// Printing brackets in matrix chain multiplication
class Multiplication(var name: Char,
    var count: Int)
{
    def this()
    {
        this('A', 0)
    }
    def showBrackets(i: Int, j: Int, brackets: Array[Array[Int]]): Unit = {
        if (i == j)
        {
            if (count != 0)
            {
                print(name.toInt + count);
            }
            else
            {
                print(name);
            }
            if (name == 'Z')
            {
                // Useful when dimension size is exceed A..Z
                name = 'A';
                count += 1;
            }
            else
            {
                // Change name
                name = (name.toInt + 1).toChar;
            }
        }
        else
        {
            print("(");
            showBrackets(i, brackets(i)(j), brackets);
            showBrackets(brackets(i)(j) + 1, j, brackets);
            print(")");
        }
    }
    def matrixChainMultiplication(dims: Array[Int], size: Int): Unit = {
        var n: Int = size - 1;
        var result: Array[Array[Int]] = Array.fill[Int](n, n)(0);
        var brackets: Array[Array[Int]] = Array.fill[Int](n, n)(0);
        var cost: Int = 0;
        var j: Int = 0;
        var len: Int = 1;
        while (len < n)
        {
            var i: Int = 0;
            while (i < n - len)
            {
                j = i + len;
                result(i)(j) = Int.MaxValue;
                var k: Int = i;
                while (k < j)
                {
                    cost = result(i)(k) + result(k + 1)(j) + dims(i) * 
                        dims(k + 1) * dims(j + 1);
                    if (cost < result(i)(j))
                    {
                        result(i)(j) = cost;
                        brackets(i)(j) = k;
                    }
                    k += 1;
                }
                i += 1;
            }
            len += 1;
        }
        this.name = 'A';
        this.count = 0;
        // Show Brackets
        showBrackets(0, n - 1, brackets);
        print("\n");
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var task: Multiplication = new Multiplication();
        var dims1: Array[Int] = Array(10, 16, 12, 6, 14);
        var dims2: Array[Int] = Array(8, 20, 16, 10, 6);
        /*
            dims = [10 , 16 , 12 , 6 , 14]
            matri× A = 10 × 16 
            matri× B = 16 × 12
            matri× C = 12 × 6
            matri× D = 6 ×  14
            --------------------
            (A(BC))D
            (16×12×6) + (10×16×6) + (10×6×14)
            =  2952  
        */
        var n: Int = dims1.length;
        task.matrixChainMultiplication(dims1, n);
        n = dims2.length;
        /*
            dims = [8 , 20 , 16 , 10 , 6]
            matri× A = 8 × 20
            matri× B = 20 × 16
            matri× C = 16 × 10
            matri× D = 10 × 6
            A(B(CD)) =  3840
            (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
        */
        task.matrixChainMultiplication(dims2, n);
    }
}

Output

((A(BC))D)
(A(B(CD)))
import Foundation;
// Swift 4 Program
// Printing brackets in matrix chain multiplication
class Multiplication
{
    var name: Character;
    var count: Int;
    init()
    {
        self.name = "A";
        self.count = 0;
    }
    func showBrackets(_ i: Int, _ j: Int, _ brackets: [
        [Int]
    ])
    {
        if (i == j)
        {
            if (self.count  != 0)
            {
                print(Int(UnicodeScalar(String(self.name))!.value) + self.count, terminator: "");
            }
            else
            {
                print(self.name, terminator: "");
            }
            if (self.name == "Z")
            {
                // Useful when dimension size is exceed A..Z
                self.name = "A";
                self.count += 1 ;
            }
            else
            {
                // Change name
                self.name =  Character(UnicodeScalar(
                    Int(UnicodeScalar(String(self.name))!.value) + i)!)

                
            }
        }
        else
        {
            print("(", terminator: "");
            self.showBrackets(i, brackets[i][j], brackets);
            self.showBrackets(brackets[i][j] + 1, j, brackets);
            print(")", terminator: "");
        }
    }
    func matrixChainMultiplication(_ dims: [Int], _ size: Int)
    {
        let n: Int = size - 1;
        var result: [
            [Int]
        ] = Array(repeating: Array(repeating: 0, count: n), count: n);
        var brackets: [
            [Int]
        ] = Array(repeating: Array(repeating: 0, count: n), count: n);
        var cost: Int = 0;
        var j: Int = 0;
        var len: Int = 1;
        while (len < n)
        {
            var i: Int = 0;
            while (i < n - len)
            {
                j = i + len;
                result[i][j] = Int.max;
                var k: Int = i;
                while (k < j)
                {
                    cost = result[i][k] + result[k + 1][j] + dims[i] * 
                        dims[k + 1] * dims[j + 1];
                    if (cost < result[i][j])
                    {
                        result[i][j] = cost;
                        brackets[i][j] = k;
                    }
                    k += 1;
                }
                i += 1;
            }
            len += 1;
        }
        self.name = "A";
        self.count = 0;
        // Show Brackets
        self.showBrackets(0, n - 1, brackets);
        print(terminator: "\n");
    }
}
func main()
{
    let task: Multiplication = Multiplication();
    let dims1: [Int] = [10, 16, 12, 6, 14];
    let dims2: [Int] = [8, 20, 16, 10, 6];
    /*
        dims = [10 , 16 , 12 , 6 , 14]
        matri× A = 10 × 16 
        matri× B = 16 × 12
        matri× C = 12 × 6
        matri× D = 6 ×  14
        --------------------
        (A(BC))D
        (16×12×6) + (10×16×6) + (10×6×14)
        =  2952  
    */
    var n: Int = dims1.count;
    task.matrixChainMultiplication(dims1, n);
    n = dims2.count;
    /*
        dims = [8 , 20 , 16 , 10 , 6]
        matri× A = 8 × 20
        matri× B = 20 × 16
        matri× C = 16 × 10
        matri× D = 10 × 6
        A(B(CD)) =  3840
        (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    */
    task.matrixChainMultiplication(dims2, n);
}
main();

Output

((A(AB))D)
(A(A(BD)))
// Kotlin Program
// Printing brackets in matrix chain multiplication
class Multiplication
{
    var name: Char;
    var count: Int;
    constructor()
    {
        this.name = 'A';
        this.count = 0;
    }
    fun showBrackets(i: Int, j: Int, 
                    brackets: Array < Array < Int >> ): Unit
    {
        if (i == j)
        {
            if (this.count != 0)
            {
                print(this.name.toInt() + this.count);
            }
            else
            {
                print(this.name);
            }
            if (this.name == 'Z')
            {
                // Useful when dimension size is exceed A..Z
                this.name = 'A';
                this.count += 1;
            }
            else
            {
                // Change name
                this.name += 1;
            }
        }
        else
        {
            print("(");
            this.showBrackets(i, brackets[i][j], brackets);
            this.showBrackets(brackets[i][j] + 1, j, brackets);
            print(")");
        }
    }
    fun matrixChainMultiplication(dims: Array < Int > , size: Int): Unit
    {
        var n: Int = size - 1;
        val result: Array < Array < Int >> = Array(n)
        {
            Array(n)
            {
                0
            }
        };
        val brackets: Array < Array < Int >> = Array(n)
        {
            Array(n)
            {
                0
            }
        };
        var cost : Int;
        var j : Int;
        var len: Int = 1;
        while (len < n)
        {
            var i: Int = 0;
            while (i < n - len)
            {
                j = i + len;
                result[i][j] = Int.MAX_VALUE;
                var k: Int = i;
                while (k < j)
                {
                    cost = result[i][k] + result[k + 1][j] + dims[i] * 
                        dims[k + 1] * dims[j + 1];
                    if (cost < result[i][j])
                    {
                        result[i][j] = cost;
                        brackets[i][j] = k;
                    }
                    k += 1;
                }
                i += 1;
            }
            len += 1;
        }
        this.name = 'A';
        this.count = 0;
        // Show Brackets
        this.showBrackets(0, n - 1, brackets);
        print("\n");
    }
}
fun main(args: Array < String > ): Unit
{
    val task: Multiplication = Multiplication();
    val dims1: Array < Int > = arrayOf(10, 16, 12, 6, 14);
    val dims2: Array < Int > = arrayOf(8, 20, 16, 10, 6);
    /*
        dims = [10 , 16 , 12 , 6 , 14]
        matri× A = 10 × 16 
        matri× B = 16 × 12
        matri× C = 12 × 6
        matri× D = 6 ×  14
        --------------------
        (A(BC))D
        (16×12×6) + (10×16×6) + (10×6×14)
        =  2952  
    */
    var n: Int = dims1.count();
    task.matrixChainMultiplication(dims1, n);
    n = dims2.count();
    /*
        dims = [8 , 20 , 16 , 10 , 6]
        matri× A = 8 × 20
        matri× B = 20 × 16
        matri× C = 16 × 10
        matri× D = 10 × 6
        A(B(CD)) =  3840
        (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    */
    task.matrixChainMultiplication(dims2, n);
}

Output

((A(BC))D)
(A(B(CD)))

Code Explanation:

Let's understand the provided Java code step by step:

  1. The Multiplication class represents the solution for the problem. It has member variables name and count to keep track of matrix names and counts.

  2. The showBrackets function is responsible for recursively printing the brackets based on the brackets matrix.

  3. The matrixChainMultiplication function implements the dynamic programming approach to find the optimal order and compute the minimum cost of matrix multiplication.

  4. In the main function, two example sequences of matrices are defined: dims1 and dims2. The matrixChainMultiplication function is called for each sequence to find the optimal order and print the brackets.

Output:

The output of the provided code for the given sequences of matrices is:

((A(BC))D)
(A(B(CD)))

These outputs represent the optimal order of matrix multiplication along with the brackets.

The problem of matrix chain multiplication involves finding the optimal order of matrix multiplication to minimize the cost. In this article, we explored a dynamic programming solution in Java for printing the brackets that represent the optimal order. By using the provided code and understanding the underlying approach, you can apply this solution to solve similar matrix chain multiplication problems in other programming languages.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment