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

C の n 項目の k 個の組み合わせをすべて生成するアルゴリズム

当面のタスクは、可能なすべての組み合わせを生成して表示するプログラムを作成することですn 個の個人の集合からの k 個の異なる人々の組み合わせ。これは、次のように動作する組み合わせ生成アルゴリズムを使用して実現できます。

アルゴリズム:

1. K のシーケンスでビットマスクを初期化します。先頭の 1: このビットマスクは、セット内の最初の K 人が最初に割り当てられることを示します。
2. ビットマスクのサイズを N ビットに変更し、末尾に N-K 個の 0 を追加します: このステップでは、セット内の n 人全員をカバーするようにビットマスクを拡張します。
3. 反復ビットマスクの可能なすべての置換を通じて: 各置換は K の異なる組み合わせを表します。

4. 各順列:

   • ビットマスク内の設定ビットのインデックスを抽出します。これらのインデックスは、現在の組み合わせのメンバーを表します。
   • 組み合わせを出力します。
5. すべての順列がなくなるまで手順 3 を繰り返します。 これのセットから K 人の可能な組み合わせをすべて生成することになります。 n.

C での実装:

#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

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