C で n 個の項目のすべての可能な k 個の組み合わせを生成するにはどうすればよいですか?

C で n 項目の考えられるすべての k 個の組み合わせを作成する

1 から n までの整数のセットが与えられた場合、タスクは、 k 個の異なる可能なすべての組み合わせを出力しますelements.

アルゴリズム:

この問題は、ビットマスク ベースのアプローチを使用して解決できます。ビットマスクは数値の表現であり、各ビットはセット内の要素の有無を示します。

アルゴリズムは次のように機能します:

1. 先頭に k を付けてビットマスクを生成します。 1 は、組み合わせの最初の k 項目を表します。
2. ビットマスクのサイズを n ビットに変更し、残りの N-K ビットを次のように設定します。 0.
3. 長さ n のビットマスクを繰り返し、各ビットをチェックします。
4. 1 に設定された各ビットについて、対応するitem.

コード:

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

void comb(int N, int K)
{
    std::string bitmask(K, 1);
    bitmask.resize(N, 0);

    do {
        for (int i = 0; i < N; ++i) {
            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

分析:

このアルゴリズムはビットマスクを操作することで組み合わせを表現できます。これは要素のセットを表現する効率的な方法です。可能なすべての組み合わせを生成する場合の時間計算量は O(n^k) です。

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