C++ Combination Generator

gen_combination.cpp

#include <iostream>
#include <stdexcept>
#include <vector>
#include <sstream>

using namespace std;

int nCk(int n, int k);

class CombinationGenerator
{
private:
    vector<int> state;
    int n, k;
    long long combination_counter;
public:
    CombinationGenerator(int n, int k);

    vector<int> next();
};

CombinationGenerator::CombinationGenerator(int n, int k)
{
    if (n < 0)
    {
        stringstream ss;
        ss << "Invalid argument: n = " << n << " < 0";
        throw invalid_argument(ss.str());
    }

    if (k < 0)
    {
        stringstream ss;
        ss << "Invalid argument: k = " << k << " < 0";
        throw invalid_argument(ss.str());
    }

    if (k > n)
    {
        stringstream ss;
        ss << "Invalid argument: k = " << k << " > n = " << n;
        throw invalid_argument(ss.str());
    }

    this->n = n;
    this->k = k;
    combination_counter = nCk(n, k);
    state.resize(k);

    for (int i = 0; i < k; i++) {
        state[i] = i;
    }
    if (k != 0) state[k - 1]--;
}

/**
 * Returns a k-combination of numbers from 0 to n-1.
 * If the last combination is generated, subsequent calls return empty vector.
 */
vector<int> CombinationGenerator::next()
{
    if (k == 0 || --combination_counter == 0)
    {
        if (combination_counter < 0) combination_counter = 0;

        vector<int> empty;
        return empty;
    }

    for (int i = k - 1; i >= 0; i--)
    {
        state[i]++;

        // If "overflow", move to the element before.
        if (state[i] > n - k + i) continue;

        // Reset the next elements.
        for (int j = i + 1; j < k; j++) state[j] = state[j - 1] + 1;
        break;
    }

    return state;
}

/**
 * Given n and k, calculate number of combination nCk.
 * If k > n, returns 0.
 * int is enough for this problem.
 */
int nCk(int n, int k)
{
    if (k > n) return 0;
    if (k * 2 > n) k = n - k;
    if (k == 0) return 1;

    int nCk = n;
    for (int i = 2; i <= k; i++)
    {
        nCk *= (n - i + 1);
        nCk /= i;
    }

    return nCk;
}