trjhtr

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> test1,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

My advice here is this: throw away your requirement of not having any state. The number sequence $binomilceil 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_errorss.str();
 

 if (set_size == 0)
 
 std::stringstream ss;
 ss << "set_size is zero";
 throw std::runtime_errorss.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());