# 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 <algorithm>
#include <functional>

template <typename Iterator>
Iterator find_next_increase_position(Iterator begin, Iterator combination_end, Iterator end);

template <typename Iterator>
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 <typename Iterator>
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<typename Iterator::value_type>());
if (pos.base() == begin)
return ++end;
return --pos.base();
}


An example:

#include <vector>

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


With output:

12435
12534
13425
13524
14523
23415
23514
24513
34512


Edit: added #includes and example

• Are you missing some #include lines? It looks like you need (at least) #include <algorithm> and #include <iterator>. Commented Jan 8, 2018 at 14:32

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 <iostream>
#include <iterator>
#include <sstream>
#include <vector>

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<size_t> 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 < 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 > set_size)
{
std::stringstream ss;
ss << "combination_size("
<< combination_size
<< ") > set_size("
<< set_size
<< ")";
throw std::runtime_error{ss.str()};
}

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

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

for (int i = (int)(m_combination_size - 2); i >= 0; --i)
{
if (m_indices[i] < m_indices[i + 1] - 1)
{
m_indices[i]++;

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

return true;
}
}

return false;
}

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

std::cout << ": ";

for (size_t i = 0; i < gen.get_combination_size(); ++i)
{
auto iter = begin;
std::cout << *iter;
}

std::cout << "\n";
}

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

• My output is correct. You forgot to count the initial combination I didn't display in my example. // I'm still reading your post Commented Jan 8, 2018 at 20:50
• @papagaga Ok got it. My bad. Commented Jan 8, 2018 at 20:51
• @papagaga Ah, of course. You first increment 12345 and only after that you print it. Commented Jan 8, 2018 at 20:53
• A stateful algorithm wasn't my purpose. I believe stateless is an interesting goal because you can parallelize efficiently. Given a sorted range as input, two rotations are enough to create another starting point. For example: thread 1: "12345", thread2: "23415" (of course it would be useful only for longer sequences) Commented Jan 9, 2018 at 9:37
• @papagaga Fair enough. Commented Jan 9, 2018 at 9:40