C++ Programming Code Examples

C++ > Arrays and Matrices Code Examples

Program to Compute Combinations using Matrix Multiplication



Program to Compute Combinations using Matrix Multiplication

1. This algorithm computes the combination using matrix multiplication method.
2. The time complexity to compute this is O(n*n*n).
3. This algorithm is very expensive to compute a combination.

This is a C++ program to compute combinations using matrix multiplication.

#include<iostream>
 
using namespace std;
 
// A function to find the factorial of a given number using matrix multiplication method.
int MatFactorial(int n)
{
	int x, j, k, matA[n+1][n+1], matB[n+1][n+1], matC[n+1][n+1], count;
	count = n;
	// Assigning numbers from 1 to n to the super diagonal indexes of the matrix.
	// Assigning result matric matC[][] to zero initially.
	for(x = 0; x < n+1; x++)
	{
		for(j = 0; j < n+1; j++)
		{
			if(j == x+1)
				matA[x][j] = x+1;
			else
				matA[x][j] = 0;
 
			// Assign matB[][] equal to initially to compute square.	
			matB[x][j] = matA[x][j];
			matC[x][j] = 0;	
		}
	}
 
	flag:
	// Multiply matA[][] and matB[][] and store the data into matC[][].
	for(x = 0; x < n+1; x++)
	{
		for(j = 0; j < n+1; j++)
		{
			for(k = 0; k < n+1; k++)
			{
				matC[x][j] += matA[x][k]*matB[k][j];
			}	
		}
	}
 
	// Assign matB as the result matrix matC[][] and then assign matC[x][j] element to zero again.
	for(x = 0; x < n+1; x++)
	{
		for(j = 0; j < n+1; j++)
		{
			matB[x][j] = matC[x][j];
			matC[x][j] = 0;	
		}
	}
 
	count--;
	// We need to compute the matA[][] raise to the power of n so if count is more than 1 then increase the power of matA[][].
	if(count > 1)
		goto flag;
 
	// If matA[][] raise to n is calculated, then return the last element of the first row of matB[][], as the factorial of n.	
	return matB[0][n];
}
 
int main()
{
	int n, r,  result;
	cout<<"A program to find combination from nCr format using matrix multiplication method:-";
	cout<<"\n\n\tEnter the value of n: ";
	cin>>n;
	cout<<"\tEnter the value of r: ";
	cin>>r;
 
	// Get result using formulae to calculate combinations.
	result = MatFactorial(n)/(MatFactorial(r)*MatFactorial(n-r));
 
	cout<<"\nThe number of possible combinations is: "<<result;
 
	return 0;
}