C の N 要素からすべての K の組み合わせを生成するにはどうすればよいですか?

組み合わせ生成: C での組み合わせの構築

組み合わせは順序のない要素のセットであり、この記事ではすべての要素を生成することに焦点を当てます。 n 個のセットから k 個の可能な組み合わせ

アルゴリズム

提供された C コードは、次のような単純なアルゴリズムを採用しています:

1. バイナリ表現: 各組み合わせはバイナリ文字列として表すことができ、設定されたビットは対応する文字列の存在を示します。 element.
2. ビットマスク初期化: 先頭に k 個の 1 と末尾に N-k 個の 0 を含むバイナリ文字列を作成します。
3. 置換: 可能なすべての置換を繰り返します。 STL prev_permutation を使用したこのバイナリ文字列function.
4. 出力: 各順列について、設定されたビットに対応する要素のインデックスを出力します。

コード実装

#include <algorithm>
#include <iostream>
#include <string>

void comb(int N, int K)
{
    std::string bitmask(K, 1); // K leading 1's
    bitmask.resize(N, 0); // N-K trailing 0's

    // print integers and permute bitmask
    do {
        for (int i = 0; i < N; ++i) // [0..N-1] integers
        {
            if (bitmask[i]) std::cout << " " << i;
        }
        std::cout << std::endl;
    } while (std::prev_permutation(bitmask.begin(), bitmask.end()));
}

int main()
{
    comb(5, 3);
}

出力

 0 1 2
 0 1 3
 0 1 4
 0 2 3
 0 2 4
 0 3 4
 1 2 3
 1 2 4
 1 3 4
 2 3 4

分析

このアルゴリズムは、バイナリ文字列と組み合わせ間の 1 対 1 対応。バイナリ表現を並べ替えることにより、可能なすべてのビットマスクの組み合わせが効果的に生成され、したがって要素のすべての可能な組み合わせが生成されます。

このアルゴリズムの複雑さは O(C(n, k)) です。ここで、C(n, k) ) は、一度に k 個ずつ取得される n 項目の組み合わせの数です。

以上がC の N 要素からすべての K の組み合わせを生成するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。