Generate next combination in lexicographic order C++'s standard library has a std::next_permutation algorithm but no next_combination. The reason behind this absence is, I guess, that one of the easiest and fastest way to generate combinations one at a time is to rely on the permutations of a vector of boolean values, which is then used as a sieve to retain the elements in the combination. The drawback is that you need to maintain some state to compute the next permutation.

Here's a try at a STL style next_combination state-less algorithm. The range [begin, end) contains the whole set of elements, and [begin, begin+k) the current combination of k elements. The next combination is generated in place.

I'd be grateful for advice and improvement suggestions. 

NB1: the algorithm depends on two invariants: [begin, begin+k] is sorted, and [begin+k, end) is sorted also.

NB2: I've tried to rely on existing STL algorithms as much as possible.

#include &lt;algorithm&gt;
#include &lt;functional&gt;

template &lt;typename Iterator&gt;
Iterator find_next_increase_position(Iterator begin, Iterator combination_end, Iterator end);

template &lt;typename Iterator&gt;
bool next_combination(Iterator begin, Iterator end, unsigned k) {
    const auto combination_end = begin+k;
    const auto next_move = find_next_increase_position(begin, combination_end, end);
    if (next_move == end) return false;
    const auto previous_value = *next_move;
    std::inplace_merge(next_move, combination_end, end);
    const auto next_rotation =
        std::rotate(next_move, std::upper_bound(next_move, end, previous_value), end);
    std::rotate(combination_end, next_rotation, end);
    return true;
}

template &lt;typename Iterator&gt;
Iterator find_next_increase_position(Iterator begin, Iterator combination_end, Iterator end) {
    auto pos = std::upper_bound(std::reverse_iterator(combination_end),
                                    std::reverse_iterator(begin),
                                    *--end,
                                    std::greater&lt;typename Iterator::value_type&gt;());
    if (pos.base() == begin)
        return ++end;
    return --pos.base();
}


An example:

#include &lt;vector&gt;

int main() {
    std::vector&lt;int&gt; test{1,2,3,4,5};
    while (next_combination(test.begin(), test.end(), 3)) {
        for (auto i : test) std::cout &lt;&lt; i;    
        std::cout &lt;&lt; std::endl;
    }
}


With output:

12435
12534
13425
13524
14523
23415
23514
24513
34512


Edit: added #includes and example
My advice here is this: throw away your requirement of not having any state. The number sequence \$\binom{i}{\lceil i \rceil}\$ grows fast, so you won't be able to deal with combinations whose state is "large". Also, I see no point doing templates here. Instead you could write a simple class that manages indices in such a way that indirection is lexicographic:

#include &lt;iostream&gt;
#include &lt;iterator&gt;
#include &lt;sstream&gt;
#include &lt;vector&gt;

class lexicographical_combination_generator {
public:
    lexicographical_combination_generator(size_t set_size,
                                          size_t combination_size);
    bool increment();
    size_t get_set_size()                      { return m_set_size; }
    size_t get_combination_size()              { return m_combination_size; }
    size_t get_combination_index(size_t index) { return m_indices[index]; }
private:
    size_t              m_set_size;
    size_t              m_combination_size;
    std::vector&lt;size_t&gt; m_indices;

    void check_arguments(size_t set_size, size_t combination_size);
};

lexicographical_combination_generator::
lexicographical_combination_generator(size_t set_size, size_t combination_size)
{
    check_arguments(set_size, combination_size);
    m_set_size = set_size;
    m_combination_size = combination_size;

    for (size_t index = 0; index &lt; m_combination_size; ++index)
    {
        m_indices.push_back(index);
    }
}

void lexicographical_combination_generator::
check_arguments(size_t set_size, size_t combination_size)
{
    if (combination_size &gt; set_size)
    {
        std::stringstream ss;
        ss &lt;&lt; "combination_size("
           &lt;&lt; combination_size
           &lt;&lt; ") &gt; set_size("
           &lt;&lt; set_size
           &lt;&lt; ")";
        throw std::runtime_error{ss.str()};
    }

    if (set_size == 0)
    {
        std::stringstream ss;
        ss &lt;&lt; "set_size is zero";
        throw std::runtime_error{ss.str()};
    }
}

bool lexicographical_combination_generator::increment()
{
    if (m_indices[m_combination_size - 1] &lt; m_set_size - 1)
    {
        m_indices[m_combination_size - 1]++;
        return true;
    }

    for (int i = (int)(m_combination_size - 2); i &gt;= 0; --i)
    {
        if (m_indices[i] &lt; m_indices[i + 1] - 1)
        {
            m_indices[i]++;

            for (int j = i + 1; j &lt; m_combination_size; ++j)
            {
                m_indices[j] = m_indices[j - 1] + 1;
            }

            return true;
        }
    }

    return false;
}

template&lt;typename Iter&gt;
void print(lexicographical_combination_generator&amp; gen, Iter begin)
{
    for (size_t i = 0; i &lt; gen.get_combination_size(); ++i)
    {
        std::cout &lt;&lt; gen.get_combination_index(i);
    }

    std::cout &lt;&lt; ": ";

    for (size_t i = 0; i &lt; gen.get_combination_size(); ++i)
    {
        auto iter = begin;
        std::advance(iter, gen.get_combination_index(i));
        std::cout &lt;&lt; *iter;
    }

    std::cout &lt;&lt; "\n";
}

int main(int argc, const char * argv[]) {
    std::vector&lt;char&gt; alphabet = { 'a', 'b', 'c', 'd', 'e' };
    lexicographical_combination_generator gen(5, 3);
    do {
        print(gen, alphabet.begin());
    } while (gen.increment());
}