在 C++ 中生成组合 [英] Generating combinations in c++

问题描述

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

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;
}

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

or a slight variation that outputs the results in an easier to follow order:

#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;
}

稍微解释一下:

它的工作原理是创建一个选择数组"(v)，我们在其中放置r选择器，然后我们创建这些选择器的所有排列，并打印相应的集合成员，如果它在 v 的当前排列中被选中.希望这会有所帮助.

It works by creating a "selection array" (v), where we place r selectors, then we create all permutations of these selectors, and print the corresponding set member if it is selected in in the current permutation of v. Hope this helps.

这篇关于在 C++ 中生成组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！