Generate next combination in lexicographic order
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());
}