Skip to main content

Matrix chain multiplication using recursion

Here given code implementation process.

/*
    C program for
    Matrix chain multiplication using recursion
*/
#include <stdio.h>
#include <limits.h>

int matrixChainMultiplication(int dims[], int i, int j)
{
	if (j <= i + 1)
	{
		return 0;
	}
	int cost = 0;
	int minValue = INT_MAX;
	for (int k = i + 1; k < j; k++)
	{
		cost = matrixChainMultiplication(dims, i, k);
		cost = cost + matrixChainMultiplication(dims, k, j);
		// Change cost
		cost = cost + dims[i] *dims[k] *dims[j];
		if (cost < minValue)
		{
			// Get new minimum value
			minValue = cost;
		}
	}
	return minValue;
}
int main(int argc, char
	const *argv[])
{
	int dims1[] = {
		10 , 16 , 12 , 6 , 14
	};
	int n = sizeof(dims1) / sizeof(dims1[0]);
	/*

	    matrix A = 10 X 16 
	    matrix B = 16 X 12
	    matrix C = 12 X 6
	    matrix D = 6 X  14
	    --------------------
	    (A(BC))D

	    (16*12*6) + (10*16*6) + (10*6*14)
	     =  2952  
	*/
	printf("\n %d", matrixChainMultiplication(dims1, 0, n - 1));
	int dims2[] = {
		8 , 20 , 16 , 10 , 6
	};
	n = sizeof(dims2) / sizeof(dims2[0]);
	/*
	    matrix A = 8 X 20
	    matrix B = 20 X 16
	    matrix C = 16 X 10
	    matrix D = 10 X 6

	    A(B(CD)) =  3840

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

	*/
	printf("\n %d", matrixChainMultiplication(dims2, 0, n - 1));
	return 0;
}

Output

 2952
 3840
/*
  Java program for
  Matrix chain multiplication using recursion
*/
public class Multiplication
{
	public int matrixChainMultiplication(int[] dims, int i, int j)
	{
		if (j <= i + 1)
		{
			return 0;
		}
		int cost = 0;
		int minValue = Integer.MAX_VALUE;
		for (int k = i + 1; k < j; k++)
		{
			cost = matrixChainMultiplication(dims, i, k);
			cost = cost + matrixChainMultiplication(dims, k, j);
			// Change cost
			cost = cost + dims[i] * dims[k] * dims[j];
			if (cost < minValue)
			{
				// Get new minimum value
				minValue = cost;
			}
		}
		return minValue;
	}
	public static void main(String[] args)
	{
		Multiplication task = new Multiplication();
		int[] dims1 = {
			10 , 16 , 12 , 6 , 14
		};
		int n = dims1.length;
		/*
		    matrix A = 10 X 16 
		    matrix B = 16 X 12
		    matrix C = 12 X 6
		    matrix D = 6 X  14
		    --------------------
		    (A(BC))D

		    (16*12*6) + (10*16*6) + (10*6*14)
		     =  2952  
		*/
		System.out.print("\n " + 
                         task.matrixChainMultiplication(dims1, 0, n - 1));
		int[] dims2 = {
			8 , 20 , 16 , 10 , 6
		};
		n = dims2.length;
		/*
		    matrix A = 8 X 20
		    matrix B = 20 X 16
		    matrix C = 16 X 10
		    matrix D = 10 X 6

		    A(B(CD)) =  3840

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

		*/
		System.out.print("\n " + 
                         task.matrixChainMultiplication(dims2, 0, n - 1));
	}
}

Output

 2952
 3840
// Include header file
#include <iostream>

#include <limits.h>

using namespace std;
/*
  C++ program for
  Matrix chain multiplication using recursion
*/
class Multiplication
{
	public: int matrixChainMultiplication(int dims[], int i, int j)
	{
		if (j <= i + 1)
		{
			return 0;
		}
		int cost = 0;
		int minValue = INT_MAX;
		for (int k = i + 1; k < j; k++)
		{
			cost = this->matrixChainMultiplication(dims, i, k);
			cost = cost + this->matrixChainMultiplication(dims, k, j);
			// Change cost
			cost = cost + dims[i] *dims[k] *dims[j];
			if (cost < minValue)
			{
				// Get new minimum value
				minValue = cost;
			}
		}
		return minValue;
	}
};
int main()
{
	Multiplication *task = new Multiplication();
	int dims1[] = {
		10 , 16 , 12 , 6 , 14
	};
	int n = sizeof(dims1) / sizeof(dims1[0]);
	/*
	    matrix A = 10 X 16 
	    matrix B = 16 X 12
	    matrix C = 12 X 6
	    matrix D = 6 X  14
	    --------------------
	    (A(BC))D
	    (16*12*6) + (10*16*6) + (10*6*14)
	     =  2952  
	*/
	cout << "\n " << task->matrixChainMultiplication(dims1, 0, n - 1);
	int dims2[] = {
		8 , 20 , 16 , 10 , 6
	};
	n = sizeof(dims2) / sizeof(dims2[0]);
	/*
	    matrix A = 8 X 20
	    matrix B = 20 X 16
	    matrix C = 16 X 10
	    matrix D = 10 X 6
	    A(B(CD)) =  3840
	    (16 X 10 X 6) + (20 X 16 X 6 ) + ( 8 X 20 X 6 ) = 3840
	*/
	cout << "\n " << task->matrixChainMultiplication(dims2, 0, n - 1);
	return 0;
}

Output

 2952
 3840
// Include namespace system
using System;
/*
  Csharp program for
  Matrix chain multiplication using recursion
*/
public class Multiplication
{
	public int matrixChainMultiplication(int[] dims, int i, int j)
	{
		if (j <= i + 1)
		{
			return 0;
		}
		int cost = 0;
		int minValue = int.MaxValue;
		for (int k = i + 1; k < j; k++)
		{
			cost = this.matrixChainMultiplication(dims, i, k);
			cost = cost + this.matrixChainMultiplication(dims, k, j);
			// Change cost
			cost = cost + dims[i] * dims[k] * dims[j];
			if (cost < minValue)
			{
				// Get new minimum value
				minValue = cost;
			}
		}
		return minValue;
	}
	public static void Main(String[] args)
	{
		Multiplication task = new Multiplication();
		int[] dims1 = {
			10 , 16 , 12 , 6 , 14
		};
		int n = dims1.Length;
		/*
		    matrix A = 10 X 16 
		    matrix B = 16 X 12
		    matrix C = 12 X 6
		    matrix D = 6 X  14
		    --------------------
		    (A(BC))D
		    (16*12*6) + (10*16*6) + (10*6*14)
		     =  2952  
		*/
		Console.Write("\n " + 
                      task.matrixChainMultiplication(dims1, 0, n - 1));
		int[] dims2 = {
			8 , 20 , 16 , 10 , 6
		};
		n = dims2.Length;
		/*
		    matrix A = 8 X 20
		    matrix B = 20 X 16
		    matrix C = 16 X 10
		    matrix D = 10 X 6
		    A(B(CD)) =  3840
		    (16 X 10 X 6) + (20 X 16 X 6 ) + ( 8 X 20 X 6 ) = 3840
		*/
		Console.Write("\n " + 
                      task.matrixChainMultiplication(dims2, 0, n - 1));
	}
}

Output

 2952
 3840
package main
import "math"
import "fmt"
/*
  Go program for
  Matrix chain multiplication using recursion
*/

func matrixChainMultiplication(dims[] int, i int, j int) int {
	if j <= i + 1 {
		return 0
	}
	var cost int = 0
	var minValue int = math.MaxInt64
	for k := i + 1 ; k < j ; k++ {
		cost = matrixChainMultiplication(dims, i, k)
		cost = cost +matrixChainMultiplication(dims, k, j)
		// Change cost
		cost = cost + dims[i] * dims[k] * dims[j]
		if cost < minValue {
			// Get new minimum value
			minValue = cost
		}
	}
	return minValue
}
func main() {

	var dims1 = [] int {
		10,
		16,
		12,
		6,
		14,
	}
	var n int = len(dims1)
	/*
	    matrix A = 10 X 16 
	    matrix B = 16 X 12
	    matrix C = 12 X 6
	    matrix D = 6 X  14
	    --------------------
	    (A(BC))D
	    (16*12*6) + (10*16*6) + (10*6*14)
	     =  2952  
	*/
	fmt.Print("\n ", 
		matrixChainMultiplication(dims1, 0, n - 1))
	var dims2 = [] int {
		8,
		20,
		16,
		10,
		6,
	}
	n = len(dims2)
	/*
	    matrix A = 8 X 20
	    matrix B = 20 X 16
	    matrix C = 16 X 10
	    matrix D = 10 X 6
	    A(B(CD)) =  3840
	    (16 X 10 X 6) + (20 X 16 X 6 ) + ( 8 X 20 X 6 ) = 3840
	*/
	fmt.Print("\n ", 
		matrixChainMultiplication(dims2, 0, n - 1))
}

Output

 2952
 3840
<?php
/*
  Php program for
  Matrix chain multiplication using recursion
*/
class Multiplication
{
	public	function matrixChainMultiplication($dims, $i, $j)
	{
		if ($j <= $i + 1)
		{
			return 0;
		}
		$cost = 0;
		$minValue = PHP_INT_MAX;
		for ($k = $i + 1; $k < $j; $k++)
		{
			$cost = $this->matrixChainMultiplication($dims, $i, $k);
			$cost = $cost + $this->matrixChainMultiplication($dims, $k, $j);
			// Change cost
			$cost = $cost + $dims[$i] * $dims[$k] * $dims[$j];
			if ($cost < $minValue)
			{
				// Get new minimum value
				$minValue = $cost;
			}
		}
		return $minValue;
	}
}

function main()
{
	$task = new Multiplication();
	$dims1 = array(10, 16, 12, 6, 14);
	$n = count($dims1);
	/*
	    matrix A = 10 X 16 
	    matrix B = 16 X 12
	    matrix C = 12 X 6
	    matrix D = 6 X  14
	    --------------------
	    (A(BC))D
	    (16*12*6) + (10*16*6) + (10*6*14)
	     =  2952  
	*/
	echo("\n ".$task->matrixChainMultiplication($dims1, 0, $n - 1));
	$dims2 = array(8, 20, 16, 10, 6);
	$n = count($dims2);
	/*
	    matrix A = 8 X 20
	    matrix B = 20 X 16
	    matrix C = 16 X 10
	    matrix D = 10 X 6
	    A(B(CD)) =  3840
	    (16 X 10 X 6) + (20 X 16 X 6 ) + ( 8 X 20 X 6 ) = 3840
	*/
	echo("\n ".$task->matrixChainMultiplication($dims2, 0, $n - 1));
}
main();

Output

 2952
 3840
/*
  Node JS program for
  Matrix chain multiplication using recursion
*/
class Multiplication
{
	matrixChainMultiplication(dims, i, j)
	{
		if (j <= i + 1)
		{
			return 0;
		}
		var cost = 0;
		var minValue = Number.MAX_VALUE;
		for (var k = i + 1; k < j; k++)
		{
			cost = this.matrixChainMultiplication(dims, i, k);
			cost = cost + this.matrixChainMultiplication(dims, k, j);
			// Change cost
			cost = cost + dims[i] * dims[k] * dims[j];
			if (cost < minValue)
			{
				// Get new minimum value
				minValue = cost;
			}
		}
		return minValue;
	}
}

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

Output

2952
3840
import sys
#  Python 3 program for
#  Matrix chain multiplication using recursion
class Multiplication :
	def matrixChainMultiplication(self, dims, i, j) :
		if (j <= i + 1) :
			return 0
		
		cost = 0
		minValue = sys.maxsize
		k = i + 1
		while (k < j) :
			cost = self.matrixChainMultiplication(dims, i, k)
			cost = cost + self.matrixChainMultiplication(dims, k, j)
			#  Change cost
			cost = cost + dims[i] * dims[k] * dims[j]
			if (cost < minValue) :
				#  Get new minimum value
				minValue = cost
			
			k += 1
		
		return minValue
	

def main() :
	task = Multiplication()
	dims1 = [10, 16, 12, 6, 14]
	n = len(dims1)
	#    matrix A = 10 X 16 
	#    matrix B = 16 X 12
	#    matrix C = 12 X 6
	#    matrix D = 6 X  14
	#    --------------------
	#    (A(BC))D
	#    (16*12*6) + (10*16*6) + (10*6*14)
	#     =  2952  
	print( task.matrixChainMultiplication(dims1, 0, n - 1))
	dims2 = [8, 20, 16, 10, 6]
	n = len(dims2)
	#    matrix A = 8 X 20
	#    matrix B = 20 X 16
	#    matrix C = 16 X 10
	#    matrix D = 10 X 6
	#    A(B(CD)) =  3840
	#    (16 X 10 X 6) + (20 X 16 X 6 ) + ( 8 X 20 X 6 ) = 3840
	print(task.matrixChainMultiplication(dims2, 0, n - 1))

if __name__ == "__main__": main()

Output

2952
3840
#  Ruby program for
#  Matrix chain multiplication using recursion
class Multiplication 
	def matrixChainMultiplication(dims, i, j) 
		if (j <= i + 1) 
			return 0
		end

		cost = 0
		minValue = (2 ** (0. size * 8 - 2))
		k = i + 1
		while (k < j) 
			cost = self.matrixChainMultiplication(dims, i, k)
			cost = cost + self.matrixChainMultiplication(dims, k, j)
			#  Change cost
			cost = cost + dims[i] * dims[k] * dims[j]
			if (cost < minValue) 
				#  Get new minimum value
				minValue = cost
			end

			k += 1
		end

		return minValue
	end

end

def main() 
	task = Multiplication.new()
	dims1 = [10, 16, 12, 6, 14]
	n = dims1.length
	#    matrix A = 10 X 16 
	#    matrix B = 16 X 12
	#    matrix C = 12 X 6
	#    matrix D = 6 X  14
	#    --------------------
	#    (A(BC))D
	#    (16*12*6) + (10*16*6) + (10*6*14)
	#     =  2952  
	print("\n ", task.matrixChainMultiplication(dims1, 0, n - 1))
	dims2 = [8, 20, 16, 10, 6]
	n = dims2.length
	#    matrix A = 8 X 20
	#    matrix B = 20 X 16
	#    matrix C = 16 X 10
	#    matrix D = 10 X 6
	#    A(B(CD)) =  3840
	#    (16 X 10 X 6) + (20 X 16 X 6 ) + ( 8 X 20 X 6 ) = 3840
	print("\n ", task.matrixChainMultiplication(dims2, 0, n - 1))
end

main()

Output

 2952
 3840
/*
  Scala program for
  Matrix chain multiplication using recursion
*/
class Multiplication()
{
	def matrixChainMultiplication(
      dims: Array[Int], 
      i: Int, j: Int): Int = {
		if (j <= i + 1)
		{
			return 0;
		}
		var cost: Int = 0;
		var minValue: Int = Int.MaxValue;
		var k: Int = i + 1;
		while (k < j)
		{
			cost = matrixChainMultiplication(dims, i, k);
			cost = cost + matrixChainMultiplication(dims, k, j);
			// Change cost
			cost = cost + dims(i) * dims(k) * dims(j);
			if (cost < minValue)
			{
				// Get new minimum value
				minValue = cost;
			}
			k += 1;
		}
		return minValue;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Multiplication = new Multiplication();
		var dims1: Array[Int] = Array(10, 16, 12, 6, 14);
		var n: Int = dims1.length;
		/*
		    matrix A = 10 X 16 
		    matrix B = 16 X 12
		    matrix C = 12 X 6
		    matrix D = 6 X  14
		    --------------------
		    (A(BC))D
		    (16*12*6) + (10*16*6) + (10*6*14)
		     =  2952  
		*/
		print("\n " + task.matrixChainMultiplication(dims1, 0, n - 1));
		var dims2: Array[Int] = Array(8, 20, 16, 10, 6);
		n = dims2.length;
		/*
		    matrix A = 8 X 20
		    matrix B = 20 X 16
		    matrix C = 16 X 10
		    matrix D = 10 X 6
		    A(B(CD)) =  3840
		    (16 X 10 X 6) + (20 X 16 X 6 ) + ( 8 X 20 X 6 ) = 3840
		*/
		print("\n " + task.matrixChainMultiplication(dims2, 0, n - 1));
	}
}

Output

 2952
 3840
import Foundation;
/*
  Swift 4 program for
  Matrix chain multiplication using recursion
*/
class Multiplication
{
	func matrixChainMultiplication(_ dims: [Int],
 	 _ i: Int,
     _ j: Int) -> Int
	{
		if (j <= i + 1)
		{
			return 0;
		}
		var cost: Int = 0;
		var minValue: Int = Int.max;
		var k: Int = i + 1;
		while (k < j)
		{
			cost = self.matrixChainMultiplication(dims, i, k);
			cost = cost + self.matrixChainMultiplication(dims, k, j);
			// Change cost
			cost = cost + dims[i] * dims[k] * dims[j];
			if (cost < minValue)
			{
				// Get new minimum value
				minValue = cost;
			}
			k += 1;
		}
		return minValue;
	}
}
func main()
{
	let task: Multiplication = Multiplication();
	let dims1: [Int] = [10, 16, 12, 6, 14];
	var n: Int = dims1.count;
	/*
	    matrix A = 10 X 16 
	    matrix B = 16 X 12
	    matrix C = 12 X 6
	    matrix D = 6 X  14
	    --------------------
	    (A(BC))D
	    (16*12*6) + (10*16*6) + (10*6*14)
	     =  2952  
	*/
	print("\n ", 
          task.matrixChainMultiplication(dims1, 0, n - 1), 
          terminator: "");
	let dims2: [Int] = [8, 20, 16, 10, 6];
	n = dims2.count;
	/*
	    matrix A = 8 X 20
	    matrix B = 20 X 16
	    matrix C = 16 X 10
	    matrix D = 10 X 6
	    A(B(CD)) =  3840
	    (16 X 10 X 6) + (20 X 16 X 6 ) + ( 8 X 20 X 6 ) = 3840
	*/
	print("\n ", 
          task.matrixChainMultiplication(dims2, 0, n - 1), 
          terminator: "");
}
main();

Output

  2952
  3840
/*
  Kotlin program for
  Matrix chain multiplication using recursion
*/
class Multiplication
{
	fun matrixChainMultiplication(dims: Array < Int > , 
                                   i: Int, j: Int): Int
	{
		if (j <= i + 1)
		{
			return 0;
		}
		var cost: Int;
		var minValue: Int = Int.MAX_VALUE;
		var k: Int = i + 1;
		while (k < j)
		{
			cost = this.matrixChainMultiplication(dims, i, k);
			cost = cost + this.matrixChainMultiplication(dims, k, j);
			// Change cost
			cost = cost + dims[i] * dims[k] * dims[j];
			if (cost < minValue)
			{
				// Get new minimum value
				minValue = cost;
			}
			k += 1;
		}
		return minValue;
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Multiplication = Multiplication();
	val dims1: Array < Int > = arrayOf(10, 16, 12, 6, 14);
	var n: Int = dims1.count();
	/*
	    matrix A = 10 X 16 
	    matrix B = 16 X 12
	    matrix C = 12 X 6
	    matrix D = 6 X  14
	    --------------------
	    (A(BC))D
	    (16*12*6) + (10*16*6) + (10*6*14)
	     =  2952  
	*/
	print("\n " + task.matrixChainMultiplication(dims1, 0, n - 1));
	val dims2: Array < Int > = arrayOf(8, 20, 16, 10, 6);
	n = dims2.count();
	/*
	    matrix A = 8 X 20
	    matrix B = 20 X 16
	    matrix C = 16 X 10
	    matrix D = 10 X 6
	    A(B(CD)) =  3840
	    (16 X 10 X 6) + (20 X 16 X 6 ) + ( 8 X 20 X 6 ) = 3840
	*/
	print("\n " + task.matrixChainMultiplication(dims2, 0, n - 1));
}

Output

 2952
 3840
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