Generate next combination in lexicographic order

Question

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

• Toby Speight: Are you missing some #include lines? It looks like you need (at least) #include <algorithm> and #include <iterator>.

Answer 1

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::advance(iter, gen.get_combination_index(i));
 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());
}

• papagaga: My output is correct. You forgot to count the initial combination I didn't display in my example. // I'm still reading your post
• coderodde: @papagaga Ok got it. My bad.
• coderodde: @papagaga Ah, of course. You first increment 12345 and only after that you print it.
• papagaga: 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)
• coderodde: @papagaga Fair enough.