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

问题描述

我一直在寻找一个源$ C ​​$下使用C ++生成组合。我发现了一些先进的codeS这个但这是只适合特定号码predefined数据。谁能给我一些提示，或者，有些想法产生的组合。作为一个例子，假设集合S = {1，2，3，...，n}的和我们挑选R = 2出来。输入将 N 和研究。在这种情况下，程序会生成长度为二的数组，像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一个简单的方法：

A simple way using 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.begin() + n - 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;
}

或轻微的变化，输出的结果更容易遵循的顺序：

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() + 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;
}

解释一下： 它的工作原理是建立一个选择阵列（ v ），这里我们把研究选择，然后我们创建的所有排列这些选择的，如果它被选中的当前排列v 打印相应的一组成员。希望这有助于。

A bit of explanation: 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屋！