Skip to main content

Printing brackets in matrix chain multiplication

Here given code implementation process.

// 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)))
Last updated on by Kalkicode




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