CombinationGenerator.cpp

#include "CombinationGenerator.h"
#include <cassert>

CombinationGenerator* g_pCombinationGen = nullptr;

//====================================================
// Purpose: Initialize Combination generator with a
//      specified n (number of elements) with k
//      elements per combination
//====================================================
void CombinationGenerator::Initialize( int n, int k )
{

    // for nCk, n must be greater k, and n must be greater than 1:
    assert( n >= k && n > 1 );

    this->n = n;
    this->k = k;
    this->m_iNumLeft = this->m_iNumCombinations = ComputeBinomialCoefficient( n, k );

    // Clear our vector to be sure:
    m_vecCurrCombination.clear();

    for( int i = 0; i < k; i++ )
    {
        m_vecCurrCombination.push_back( i );
    }

}

//====================================================
// Purpose: Initializer overload, number of comb.
//      have already been calculated.
//====================================================
void CombinationGenerator::Initialize( int n, int k, unsigned long long numCombinations )
{
    assert( n >= k && n > 1);
    this->n = n;
    this->k = k;

    this->m_iNumLeft = this->m_iNumCombinations = numCombinations;


    m_vecCurrCombination.clear();

    for( int i = 0; i < k; i++ )
    {
        m_vecCurrCombination.push_back(i);
    }

}

//====================================================
// Purpose: Calculate nCk using the minimum amount of
//      memory:
//====================================================
unsigned long long CombinationGenerator::ComputeBinomialCoefficient( int n, int k )
{
    // Another run-time assert in case we decide to call this separately at some point:
    assert( n > k && n > 1 );

    // Exploit the symmetry in the line x = k/2:
    if( k > n - k )
        k = n - k;

    unsigned long long c(1);
    // Perform the product over the space i = [1...k]
    for( int i = 1; i < k+1; i++ )
    {
        c *= n - (k - i);
        c /= i;
    }

    return c;

}

//====================================================
// Purpose: How many more combinations have we got
//      left?
//====================================================
unsigned long long CombinationGenerator::GetNumLeft()
{
    return m_iNumLeft;
}

//====================================================
// Purpose: Have we finished creating combinations?
//====================================================
bool CombinationGenerator::IsFinished()
{
    return( m_iNumLeft == 0 );
}

//====================================================
// Purpose: Compute our next combination:
//====================================================
std::vector<int> CombinationGenerator::NextCombination()
{
    // If this is the first combination, return the original
    // vector:
    if( m_iNumLeft == m_iNumCombinations )
    {
        m_iNumLeft -= 1;
        return m_vecCurrCombination;
    }

    int i = k - 1;
    while( m_vecCurrCombination[i] == n - k + i )
    {
        i--;
    }

    m_vecCurrCombination[i] += 1;

    for( int j = i; j < k; j++ )
    {
        m_vecCurrCombination[j] = m_vecCurrCombination[i] + j - i;
    }

    m_iNumLeft -= 1;

    return m_vecCurrCombination;

}