To make it more complete, the following answer covers the case that the data set contains duplicate values. The function is written close to the style of std::next_permutation() so that it is easy to follow up.
template< class RandomIt >
bool next_combination(RandomIt first, RandomIt n_first, RandomIt last)
{
if (first == last || n_first == first || n_first == last)
{
return false;
}
RandomIt it_left = n_first;
--it_left;
RandomIt it_right = n_first;
bool reset = false;
while (true)
{
auto it = std::upper_bound(it_right, last, *it_left);
if (it != last)
{
std::iter_swap(it_left, it);
if (reset)
{
++it_left;
it_right = it;
++it_right;
std::size_t left_len = std::distance(it_left, n_first);
std::size_t right_len = std::distance(it_right, last);
if (left_len < right_len)
{
std::swap_ranges(it_left, n_first, it_right);
std::rotate(it_right, it_right+left_len, last);
}
else
{
std::swap_ranges(it_right, last, it_left);
std::rotate(it_left, it_left+right_len, n_first);
}
}
return true;
}
else
{
reset = true;
if (it_left == first)
{
break;
}
--it_left;
it_right = n_first;
}
}
return false;
}
The full data set is represented in the range [first, last). The current combination is represented in the range [first, n_first) and the range [n_first, last) holds the complement set of the current combination.
As a combination is irrelevant to its order, [first, n_first) and [n_first, last) are kept in ascending order to avoid duplication.
The algorithm works by increasing the last value A on the left side by swapping with the first value B on the right side that is greater than A. After the swapping, both sides are still ordered. If no such value B exists on the right side, then we start to consider increasing the second last on the left side until all values on the left side are not less than the right side.
An example of drawing 2 elements from a set by the following code:
std::vector<int> seq = {1, 1, 2, 2, 3, 4, 5};
do
{
for (int x : seq)
{
std::cout << x << " ";
}
std::cout << "\n";
} while (next_combination(seq.begin(), seq.begin()+2, seq.end()));
gives:
1 1 2 2 3 4 5
1 2 1 2 3 4 5
1 3 1 2 2 4 5
1 4 1 2 2 3 5
1 5 1 2 2 3 4
2 2 1 1 3 4 5
2 3 1 1 2 4 5
2 4 1 1 2 3 5
2 5 1 1 2 3 4
3 4 1 1 2 2 5
3 5 1 1 2 2 4
4 5 1 1 2 2 3
It is trivial to retrieve the first two elements as the combination result if needed.