C の `std::next_permutation` を使用して、指定されたサイズのすべての組み合わせを生成するにはどうすればよいでしょうか?

C での組み合わせの生成

組み合わせの作成には、選択の順序を考慮せずに、指定されたセットから要素のサブセットを選択することが含まれます。 C を使用して組み合わせを生成するタスクに直面した場合、次の点を考慮することが重要です:

問題定義:

集合 S = {1, 2, 3 が与えられた場合, ..., n} と値 r (r はセットから選択される要素の数) を使用して、指定された長さ r の可能なすべての組み合わせを生成することを目的としています。 set.

解決策:

この問題を解決する 1 つのアプローチは、C 標準ライブラリの std::next_permutation 関数を使用することです。この関数を使用すると、要素のベクトルのすべての順列を生成できます。この関数を利用すると、選択した要素を表すブール値のベクトルを作成できます。

実装:

std::next_permutation:

#include <iostream>
#include <vector>

int main() {
    int n, r;
    std::cin >> n >> 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;
}

この実装では、長さ n のベクトルを作成し、最後の r 要素を次のように埋めます。 真実。次に、 std::next_permutation 関数を使用して、ベクトルの可能なすべての置換を生成します。各順列について、ベクトル内の真の値に対応する要素を出力します。

説明:

このアプローチは、「選択配列」 (v) を作成することで機能します。 r セレクターを配置する場所。次に、これらのセレクターのすべての順列を生成し、v の現在の順列で選択されている場合は、対応するセット メンバーを出力します。

std::next_permutation 関数を利用することで、長さ r のすべての組み合わせを効率的に生成できます。指定されたセット。

以上がC の `std::next_permutation` を使用して、指定されたサイズのすべての組み合わせを生成するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。