前言

C++代码示例：组合数简单生成工具。

---

代码仓库

• yezhening/Programming-examples: 编程实例 (github.com)
• Programming-examples: 编程实例 (gitee.com)

---

内容

• 简单地生成组合数
• 有详细的步骤解析

---

代码（有详细注释）

ccombination.cpp

#include <vector>
#include <iostream>using std::cout;
using std::endl;
using std::vector;class CCombination
{
public:CCombination(const int &n, const int &m) : n(n), m(m), curComb(0), combCount(0) {}bool next(){// 第一次进入初始化当前组合，如m=3，this->curComb为012，从012开始遍历if (this->curComb.empty() == true){for (int i = 0; i < this->m; ++i){this->curComb.push_back(i);}++this->combCount;return true;}// 1. 从右向左，找到第一个不存有自己最终内容的位置// 如n=5，m=3，curPos为索引为3-1=2的位置，从该位置的数开始递增，即先从右边的数开始递增，递增完再到左边的数// curPos >= 0：防止越界// this->curComb.at(curPos) == this->n - this->m + curPos：因为是组合数，无序，不存有自己最终内容指的是在索引2，只能取到5-3+2=4，索引1取到5-3+1=3，索引0取到5-3+0=2// 继续理解：比如012，前面占了01两个位置，最后的位置能取到最大值4，第二个位置因为右边的位置占位，为了保证不重复，最大值取到3，以此类推// 即为了保证不重复，索引0位置取值范围0~2，1位置0~3，2位置0~4，位置达到这个数说明到了最终位置，位置应该减一，用其左边的数递增int curPos = this->m - 1;while ((curPos >= 0) && (this->curComb.at(curPos) == this->n - this->m + curPos)){--curPos;}if (curPos < 0){return false; // 已经遍历所有组合}// 2.把这个位置上的数值加1++this->curComb.at(curPos);// 3. 后面的数值递增// 指的是当前位置+1后，其右边的数“归位”，只能从比它大1的数开始，否则会重复，如 014 -> 023， 034 -> 123for (int right = curPos + 1; right < this->m; ++right){this->curComb.at(right) = this->curComb.at(right - 1) + 1;}++this->combCount;return true;}inline void printCurComb(){for (const int c : this->curComb){cout << c << " ";}cout << endl;}inline void printCombCount(){cout << this->combCount << endl;}private:const int n; // 从n个取m个const int m;vector<int> curComb; // 当前组合，存储组合的索引int combCount;       // 组合数的数量
};int main()
{const int n = 5;const int m = 3;CCombination comb(n, m);while (comb.next()){comb.printCurComb();}comb.printCombCount();return 0;
}

---

编译和运行命令

g++ -o ccombination ccombination.cpp
./ccombination.exe

---

结果

---

总结

C++代码示例：组合数简单生成工具。

---

参考资料

• 学校《高级算法设计与分析》课程课件的算法思路

---

作者的话

• 感谢参考资料的作者/博主
• 作者：夜悊
• 版权所有，转载请注明出处，谢谢~
• 如果文章对你有帮助，请点个赞或加个粉丝吧，你的支持就是作者的动力~
• 文章在描述时有疑惑的地方，请留言，定会一一耐心讨论、解答
• 文章在认识上有错误的地方, 敬请批评指正
• 望读者们都能有所收获

---