C でビット操作を使用して組み合わせを効率的に生成するにはどうすればよいですか?-C++-php.cn

C でビット操作を使用して組み合わせを効率的に生成するにはどうすればよいですか?

Linda Hamilton

リリース： 2024-11-29 04:14:11

オリジナル

917 人が閲覧しました

How Can I Efficiently Generate Combinations in C Using Bit Manipulation?

C での組み合わせの生成 : 包括的なソリューション

組み合わせの生成は、セットから特定の数の要素を選択することを伴う基本的なプログラミングタスクです。。たとえば、セット S = {1, 2, 3, 4, 5} があり、サイズ r = 2 の組み合わせを生成したい場合、出力には (1, 2)、(1, 3) のような組み合わせが含まれます。

C を使用して組み合わせを生成する効果的な方法の 1 つは、ビット操作を使用することです。セット要素を表す長さ n のブール値のベクトルを初期化し、最初の r 要素を true で埋めることができます。これは、対応する要素が現在の組み合わせで選択されていることを意味します。

次のステップでは、std::next_permutation 関数を使用して、この選択ベクトルのすべての順列を作成します。順列ごとに、要素が選択されているかどうか (ベクトル内の true 値によって示される) を確認し、対応する要素を出力します。すべての順列を反復処理することで、考えられるすべての組み合わせを生成できます。

このアプローチを使用したコードスニペットは次のとおりです:

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

ログイン後にコピー

あるいは、std::prev_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(), 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;
}

ログイン後にコピー

これらの手法を活用することで、効率的にC での組み合わせにより、さまざまなアルゴリズムアプリケーションに強力なツールを提供します。

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