k-combinations in lexicographic order (using given algorithm)

I already solved the problem, but it seems my code is too awkward, and with a different approach there could be a more elegant solution.

Notice that the general algorithm is described in the instructions:

This is the problem description:


Given unsigned integers 0 ≤ k ≤ n, generate all the k-combinations of
the n objects, numbered 1, 2, ... , and n, using the following
algorithm:


Starting with the combination 1, 2, ..., k, the next combination is
found by scanning the current combination from right to left so as to
locate the rightmost element that has not yet attained its maximum
value. This element is incremented by one, and all positions to its
right are reset to the lowest values possible.


Each line contains a set of n and k which separated with at least one
space.


For each case, the first line is a prompt as following: “case 1:”. The
next lines are all of the combinations. Notice that one line for one
combination and list the results in ascending order. You don’t have to
print any thing if the result is null. The last line of each case is
an empty line, even if the result is null.

```
#include
#include
#include
#include

int combination_find(std::vector combination, int max_val);
void combination_inc(std::vector& combination, const int& pos, const int& max_val);

int main()
{
int round = 0;
int n, k;
while (std::cin >> n >> k)
{
//init
std::vector combination;
int i = 0;
while (i (std::cout, " "));
std::cout combination, int max_val)
{
if (combination.empty()) { return -1; }
if (combination.back() != max_val)
{
return (combination.size() - 1);
}
else
{
combination.pop_back();
return combination_find(combination, --max_val);
}
}

void combination_inc(std::vector& combination, const int& pos, const int& max_val)
{
int val = combination[pos];
for (unsigned i = pos; i < combination

combination_find() takes \$O(K^2)\$ time and space because of the pass by value. This is unnecessary overhead and can cause trouble when K is large. Instead we can easily find the position iteratively.

int combination_find(const std::vector &combination, int max_val) {
  for (int i = combination.size() - 1; i >= 0; --i, --max_val) {
    if (combination[i] != max_val)
      return i;
  }
  return -1;
}

This also allows us to pass the vector by reference.

A few more minor points

• combination_inc() does not need max_val as a parameter

• The push_back()s in the beginning can be replaced with std::iota in C++ 11

• Perhaps it is better to combine the find and inc into a single next_combination which returns true if the combination has been updated, similar to the behaviour of std::next_permutation. The behaviour of combination_inc to require pos as an argument and modifying it through main() is strange to say the least.

StackExchange Code Review Q#153831, answer score: 3