`std::next_permutation` と `std::prev_permutation` を使用して C で組み合わせを効率的に生成するにはどうすればよいですか?-C++-php.cn

`std::next_permutation` と `std::prev_permutation` を使用して C で組み合わせを効率的に生成するにはどうすればよいですか?

Susan Sarandon

リリース： 2024-12-03 13:05:12

オリジナル

482 人が閲覧しました

How Can I Efficiently Generate Combinations in C Using `std::next_permutation` and `std::prev_permutation`?

C での組み合わせの生成

問題の概要

組み合わせの生成は、さまざまな言語で一般的な操作です。プログラミングシナリオ。これは、より大きなコレクションから指定された数の要素を含むセットを作成することで構成されます。この記事では、C で組み合わせを生成するという課題に取り組む方法について説明します。

std::next_permutation による解決策

効果的なアプローチの 1 つは、std::next_permutation 関数を活用することです。 C 標準ライブラリから。実装は次のとおりです。

#include <iostream>
#include <algorithm>
#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;
}

ログイン後にコピー

この解決策は、選択配列 (v) を作成し、r 個のセレクターを最後の r 位置に配置することから始まります。 std::next_permutation 関数は、これらのセレクターのすべての置換を生成します。順列ごとに、選択した位置に対応するセットのメンバーを出力します。

std::prev_permutation の代替

組み合わせを別の形式で出力する必要がある場合順序を変更するには、代わりに std::prev_permutation の使用を検討してください:

#include <iostream>
#include <algorithm>
#include <vector>

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

ログイン後にコピー

Thisバリエーションを使用すると、組み合わせの順序が交互になり、出力が解釈しやすくなります。

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