 # 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[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; } ``` 