在 C++ 中生成组合

I have been searching a source code for generating combination using c++. I found some advanced codes for this but that is good for only specific number predefined data. Can anyone give me some hints, or perhaps, some idea to generate combination. As an example, suppose the set S = { 1, 2, 3, ...., n} and we pick r= 2 out of it. The input would be n and r.In this case, the program will generate arrays of length two, like 5 2 outputs 1 2, 1 3, etc.. I had difficulty in constructing the algorithm. It took me a month thinking about this.

推荐答案

使用std::next_permutation的简单方法:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    int n, r;
    std::cin >> n;
    std::cin >> r;

    std::vector<bool> v(n);
    std::fill(v.end() - r, v.end(), true);

    do {
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                std::cout << (i + 1) << " ";
            }
        }
        std::cout << "
";
    } while (std::next_permutation(v.begin(), v.end()));
    return 0;
}

或以更易于遵循的顺序输出结果的轻微变化:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
   int n, r;
   std::cin >> n;
   std::cin >> r;

   std::vector<bool> v(n);
   std::fill(v.begin(), v.begin() + r, true);

   do {
       for (int i = 0; i < n; ++i) {
           if (v[i]) {
               std::cout << (i + 1) << " ";
           }
       }
       std::cout << "
";
   } while (std::prev_permutation(v.begin(), v.end()));
   return 0;
}