You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
130 lines
3.0 KiB
C++
130 lines
3.0 KiB
C++
/*
|
|
* C++ Program to Compute Combinations using Matrix Multiplication
|
|
*/
|
|
#include<iostream>
|
|
#define ll long long
|
|
using namespace std;
|
|
|
|
// Matrix C;ass
|
|
template <class T>
|
|
class Matrix
|
|
{
|
|
public:
|
|
int m, n;
|
|
T *data;
|
|
Matrix (int m, int n) ;
|
|
Matrix (const Matrix <T> &matrix);
|
|
const Matrix <T> &operator=(const Matrix<T> &A);
|
|
const Matrix <T> operator*(const Matrix<T> &A);
|
|
const Matrix <T> operator^(int P);
|
|
~Matrix();
|
|
};
|
|
//Constructor
|
|
template <class T>
|
|
Matrix <T>::Matrix(int m, int n)
|
|
{
|
|
this->m = m;
|
|
this->n = n;
|
|
data = new T[m * n];
|
|
}
|
|
//Constructor
|
|
template <class T>
|
|
Matrix <T>::Matrix (const Matrix <T> &A)
|
|
{
|
|
this->m = A.m;
|
|
this->n = A.n;
|
|
data = new T[m * n];
|
|
for (int i = 0; i < m * n; i++)
|
|
data[i] = A.data[i];
|
|
}
|
|
//Destructor
|
|
template <class T>
|
|
Matrix <T>::~Matrix()
|
|
{
|
|
delete [] data;
|
|
}
|
|
|
|
template <class T>
|
|
const Matrix <T> &Matrix <T>::operator=(const Matrix <T> &A)
|
|
{
|
|
if (&A != this)
|
|
{
|
|
delete [] data;
|
|
m = A.m;
|
|
n = A.n;
|
|
data = new T[m * n];
|
|
for (int i = 0; i < m * n; i++)
|
|
data[i] = A.data[i];
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
template <class T>
|
|
const Matrix <T> Matrix <T>::operator*(const Matrix <T> &A)
|
|
{
|
|
Matrix C (m, A.n);
|
|
for (int i = 0; i < m; ++i)
|
|
{
|
|
for (int j = 0; j < A.n; ++j)
|
|
{
|
|
C.data[i * C.n + j] = 0;
|
|
for (int k = 0; k < n; ++k)
|
|
C.data[i * C.n + j] = C.data[i * C.n + j] + (data[i * n + k] * A.data[k * A.n + j]);
|
|
}
|
|
}
|
|
return C;
|
|
}
|
|
|
|
template <class T>
|
|
const Matrix <T> Matrix <T>::operator^(int P)
|
|
{
|
|
if (P == 1)
|
|
return (*this);
|
|
if (P & 1)
|
|
return (*this) * ((*this) ^ (P - 1));
|
|
Matrix B = (*this) ^ (P/2);
|
|
return B * B;
|
|
}
|
|
|
|
//Compute Combinations
|
|
ll C(int n, int r)
|
|
{
|
|
Matrix <ll> M(r + 1,r + 1);
|
|
for (int i = 0; i < (r + 1) * (r + 1); i++)
|
|
M.data[i] = 0;
|
|
M.data[0] = 1;
|
|
for (int i = 1; i < r + 1; i++)
|
|
{
|
|
M.data[i * (r + 1) + i - 1] = 1;
|
|
M.data[i * (r + 1) + i] = 1;
|
|
}
|
|
return (M ^ n).data[r * (r + 1)];
|
|
}
|
|
|
|
//Main
|
|
int main()
|
|
{
|
|
int n, r, m;
|
|
while (1)
|
|
{
|
|
cout<<"Enter total number of objects:(0 to exit) ";
|
|
cin>>n;
|
|
if (n == 0)
|
|
break;
|
|
cout<<"Enter number of objects to be chosen: ";
|
|
cin>>r;
|
|
cout<<"Number of Combinations: "<<C(n, min(r, n - r))<<endl;
|
|
}
|
|
}
|
|
|
|
/*
|
|
Enter total number of objects:(0 to exit) 10
|
|
Enter number of objects to be chosen: 2
|
|
45
|
|
Enter total number of objects:(0 to exit) 50
|
|
Enter number of objects to be chosen: 17
|
|
9847379391150
|
|
Enter total number of objects:(0 to exit) 19
|
|
Enter number of objects to be chosen: 8
|
|
75582
|
|
Enter total number of objects:(0 to exit) 0
|