#include <iostream>
#include <vector>

#define LIKELY(x)       __builtin_expect(!!(x), 1)
#define UNLIKELY(x)     __builtin_expect(!!(x), 0)


class PythonCombinator
{
public:
    PythonCombinator(size_t k, std::vector<int> items, bool print)
        : k(k)
        , n(items.size())
        , items(std::move(items))
        , print(print)
    {
        curr.resize(k);
        for (size_t i = 0; i < k; i++) {
            curr[i] = i;
        }
    }

    void generate() noexcept
    {
        std::cout << "k=" << k << ", n=" << n << ", print=" << print << "\n";
        size_t count = generate_impl();
        std::cout << "total: " << count << "\n";
    }

private:
    // алгоритм
    bool generate_one() noexcept
    {
        ssize_t i, j;
        /* Scan indices right-to-left until finding one that is not
           at its maximum (i + n - r). */
        for (i = k - 1; i >= 0 && curr[i] == i + n - k; i--)
            ;

        /* If i is negative, then the indices are all at
           their maximum value and we're done. */
        if (i < 0)
            return false;

        /* Increment the current index which we know is not at its
           maximum.  Then move back to the right setting each index
           to its lowest possible value (one higher than the index
           to its left -- this maintains the sort order invariant). */
        curr[i]++;
        for (j = i + 1; j < k; j++)
            curr[j] = curr[j - 1] + 1;

        return true;
    }

    size_t generate_impl() noexcept __attribute((noinline))
    {
        size_t count = 0;
		count++;
		print_current();
        while (generate_one()) {
            count++;
            print_current();
        }

        return count;
    }

    void print_current() noexcept 
    {
        if (UNLIKELY(print)) {
            for (size_t i = 0; i < k; i++) {
                std::cout << items[curr[i]] << " ";
            }
            std::cout << "\n";
        }
    }

private:
    const size_t k;
    const size_t n;
    const std::vector<int> items;
    const bool print;
    std::vector<size_t> curr;
    size_t count = 0;
};


std::vector<int> iota(size_t n)
{
    std::vector<int> rv(n);
    for (size_t i = 0; i < n; i++) {
        rv[i] = i + 1;
    }
    return rv;
}

int main(int argc, char* argv[])
{
    std::cout.sync_with_stdio(false);
    size_t k = 3;
    int n = 4;
    bool print = true;
    if (argc > 2) {
        k = atol(argv[1]);
        n = atol(argv[2]);
    }
    if (argc > 3) {
        print = argv[3][0] == 'p';
    }
    PythonCombinator comb{k, iota(n), print};
    comb.generate();
    return 0;
}