問題描述

我一直在尋找使用 C++ 生成組合的源代碼.我為此找到了一些高級代碼，但這僅適用于特定數(shù)量的預(yù)定義數(shù)據(jù).誰能給我一些提示，或者一些產(chǎn)生組合的想法.例如，假設(shè)集合 S = { 1, 2, 3, ...., n} 并且我們從中選出 r=2.輸入將是 n 和 r.在這種情況下，程序?qū)⑸砷L度為 2 的數(shù)組，例如 5 2 輸出 1 2、1 3 等.我有算法構(gòu)建困難.我花了一個月的時間思考這個問題.

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

或以更易于遵循的順序輸出結(jié)果的輕微變化:

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

稍微解釋一下:

它的工作原理是創(chuàng)建一個選擇數(shù)組"(v)，我們在其中放置r選擇器，然后我們創(chuàng)建這些選擇器的所有排列，并打印相應(yīng)的集合成員，如果它在 v 的當(dāng)前排列中被選中.希望這會有所幫助.

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.

這篇關(guān)于在 C++ 中生成組合的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網(wǎng)！