#include <iostream>
#include <stack>
#include <vector>

//#include <boost/container/small_vector.hpp>
//#include <boost/container/static_vector.hpp>

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


class NonRecursiveCombinator
{
public:
    NonRecursiveCombinator(size_t k, std::vector<int> items, bool print)
        : k(k)
        , n(items.size())
        , items(std::move(items))
        , print(print)
    {
        curr.resize(k);
    }

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

private:
    // алгоритм
    void generate_impl() noexcept
    {
        struct State {
            size_t val;
        };
        //std::stack<State, boost::container::small_vector<State, 1000>> stack;
        //std::stack<State, std::vector<State>> stack;
        std::stack<State> stack; // deque; 2nd fastest
        //std::stack<State, boost::container::static_vector<State, 1000>> stack; // fastest
        size_t pos = 0;
        size_t limit = n - k + pos + 1;
        size_t val = 0;
        while (true) {
            for (; val < limit; val++) {
                curr[pos] = val;
                if (pos == k - 1) {
                    print_current();
                }
                else {
                    stack.push({val + 1});
                    pos++;
                    limit++;
                }
            }
            if (stack.empty())
                break;
            val = stack.top().val;
            stack.pop();
            pos--;
            limit--;
        }
    }

    void print_current() noexcept
    {
        count++;
        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';
    }
    NonRecursiveCombinator comb{k, iota(n), print};
    comb.generate();
    return 0;
}

#include <iostream>
#include <vector>

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


class NonRecursiveCombinator
{
public:
    NonRecursiveCombinator(size_t k, std::vector<int> items, bool print)
        : k(k)
        , n(items.size())
        , items(std::move(items))
        , print(print)
    {
        curr.resize(k);
    }

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

private:
    // алгоритм
    void generate_impl() noexcept
    {
        size_t pos = 0;
        size_t limit = n - k + pos + 1;
        size_t val = 0;
        while (true) {
            for (; val < limit; val++) {
                curr[pos] = val;
                if (pos == k - 1) {
                    print_current();
                }
                else {
                    pos++;
                    limit++;
                }
            }
            if (pos == 0)
                break;
            pos--;
            limit--;
            val = curr[pos] + 1;
        }
    }

    void print_current() noexcept
    {
        count++;
        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';
    }
    NonRecursiveCombinator comb{k, iota(n), print};
    comb.generate();
    return 0;
}