3
\$\begingroup\$

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

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

int main()
{
    int round = 0;
    int n, k;
    while (std::cin >> n >> k)
    {
        //init
        std::vector<int> combination;
        int i = 0;
        while (i < k)
        {
            combination.push_back(++i);
        }
        std::cout << "case " << ++round << ": " << std::endl;
        while(1)
        {
            //writes (upon conditional so that the print of empty vectors doesn't mess up the text formatting0
            if (!combination.empty())
            {
                std::copy(combination.begin(), combination.end(), std::ostream_iterator<int>(std::cout, " "));
                            std::cout << std::endl;
            }
            //check
            int pos = combination_find(combination, n);
            if (pos < 0) {break;}
            //increment
            combination_inc(combination, pos, n);
        }
        std::cout << std::endl;
    }
}

int combination_find(std::vector<int> 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<int>& combination, const int& pos, const int& max_val)
{
    int val = combination[pos];
    for (unsigned i = pos; i < combination.size(); ++i)
    {
        combination[i] = ++val;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Vogel612 Jan 29 '17 at 14:00
3
\$\begingroup\$

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<int> &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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.