c++で組合せを生成する

質問

私はc++を使用して組み合わせを生成するためのソースコードを検索しています。このためのいくつかの高度なコードを見つけましたが、それは特定の数の事前定義されたデータにのみ適しています。どなたか、組合せを生成するためのヒントというか、アイデアを教えていただけませんか？例として、集合S = { 1, 2, 3, ..., n}からr= 2を選ぶとする。入力は次のようになる。 n となり r .この場合、プログラムは5 2 outputs 1 2, 1 3, などのように長さ2の配列を生成することになります。アルゴリズムの組み立てに苦労しました。これを考えるのに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 セレクタを配置した後、これらのセレクタのすべての並べ換えを作成し、対応するセットメンバが現在の v . これが役に立つことを願っています。