在C ++中生成组合

一尘不染

在C ++中生成组合

algorithm

我一直在搜索使用c
++生成组合的源代码。我为此找到了一些高级代码，但这仅适用于特定数量的预定义数据。任何人都可以给我一些提示，或者可能是一些产生组合的想法。例如，假设集合S
= {1，2，3，....，n}，我们从中选出r = 2。输入为n和r。在这种情况下，程序将生成长度为2的数组，例如5 2输出1 2、1
3等。我在构造算法时遇到了困难。我花了一个月的时间思考这个问题。

阅读 315

2020-07-28

共1个答案

一尘不染

使用的简单方法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 << "\n";
    } 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 << "\n";
   } while (std::prev_permutation(v.begin(), v.end()));
   return 0;
}

一点解释：

它的工作方式是创建一个“选择数组”（v），在其中放置r选择器，然后创建这些选择器的所有排列，如果在当前的排列中被选中，则打印相应的set成员v。希望这可以帮助。

2020-07-28