//The Combination Generator Class#include < vector >
using namespace std;
typedef unsigned long long uint64;
class CombinationGenerator
{
public:
CombinationGenerator(int, int);
uint64 getNumLeft() const;
bool hasMore() const;
uint64 getTotal() const;
vector getNext();
private:
void reset();
uint64 getFactorial(int) const;
vector indices;
int n, r;
uint64 numLeft, total;
};
//--------------------------------------------//The Constructor: Arguments n and r of nCr//--------------------------------------------CombinationGenerator::CombinationGenerator(int n, int r)
{
if (r > n || n <>n = n;
this->r = r;
indices.resize(r);
uint64 nFact = getFactorial (n);
uint64 rFact = getFactorial (r);
uint64 nminusrFact = getFactorial (n - r);
total = nFact/(rFact*nminusrFact);
reset ();
}
//------// Reset//------void CombinationGenerator::reset()
{
for (int i = 0; i < numleft =" total;" style="color: rgb(0, 153, 0);">//------------------------------------------------
// Return number of combinations not yet generated//------------------------------------------------uint64 CombinationGenerator::getNumLeft() const
{
return numLeft;
}
//-----------------------------// Are there more combinations?//-----------------------------bool CombinationGenerator::hasMore() const
{
return numLeft>0;
}
//------------------------------------// Return total number of combinations//------------------------------------uint64 CombinationGenerator::getTotal() const
{
return total;
}
//------------------// Compute factorial//------------------uint64 CombinationGenerator::getFactorial(int n) const
{
uint64 fact =1;
for (int i = n; i > 1; i--) {
fact = fact*i;
}
return fact;
}
//--------------------------------------------------------// Generate next combination //--------------------------------------------------------vector CombinationGenerator::getNext()
{
if (numLeft==total) {
numLeft = numLeft-1;
return indices;
}
int i = r - 1;
while (indices[i] == n - r + i) {
i--;
}
indices[i] = indices[i] + 1;
for (int j = i + 1; j < r; j++) {
indices[j] = indices[i] + j - i;
}
numLeft = numLeft-1;
return indices;
}
///////////////Test Program/////////////////////#include < iostream >
#include "CombinationGenerator.h"
using namespace std;
int main()
{
int myints[] = {44,67,23,74};
vector
myvector (myints, myints+4);
sort (myvector.begin(), myvector.end(), greater());
/////////Generate 4C3 combinations///////////////
CombinationGenerator x(myvector.size(), 3);
while (x.hasMore ()) {
vector indices = x.getNext ();
for (int i = 0; i < indices.size(); i++) {
cout << myvector[indices[i]] <<" ";
}
cout <<endl;
}
getchar();
return 0;
}
Download Source