如何從 C 中的 N 個元素產生所有 K 組合？

組合產生：在C 中構造組合

組合是缺乏順序的元素集合，在本文中，我們將重點放在生成所有一組n 中可能的 k個組合

演算法

提供的C 程式碼採用簡單的演算法：

1. 二元化表示：
2. 位元遮罩初始化： 建立一個具有 k 個前導 1 和 N-k 個尾隨 0 的二進位字串。
3. 排列： 迭代所有可能的排列使用 STL prev_permutation 的二進位字串函數。
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

分析

演算法利用了以下優勢：二進位字串和組合之間的一一對應關係。透過排列二進位表示，它有效地產生所有可能的位元遮罩組合，從而產生所有可能的元素組合。

此演算法的複雜度為 O(C(n, k))，其中 C(n, k ) 是一次取 k 個 n 項的組合數。

以上是如何從 C 中的 N 個元素產生所有 K 組合？的詳細內容。更多資訊請關注PHP中文網其他相關文章！