如何从 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中文网其他相关文章！