C++ 实现排列组合

说明

该文章只为自己记录学习用

参考

极客时间程序员的数学基础课第7、8讲

排列

代码实现

#include <iostream> #include <vector> using namespace std; template <typename T> class Permutation { public: typedef vector<T> Sequence; typedef vector<bool> BitMap; public: // 从序列sourceSeq中选取m个元素的排列 vector<Sequence> permutation(const Sequence &sourceSeq, int m) { if (sourceSeq.size() < m || m <= 0) return {}; vector<Sequence> totalSeq; Sequence targetSeq; BitMap bitMap(sourceSeq.size(), false); permutation(sourceSeq, m, targetSeq, totalSeq, bitMap); return totalSeq; } private: void permutation(const Sequence &sourceSeq, int m, Sequence &targetSeq, vector<Sequence> &totalSeq, BitMap &bitMap) { // 已经取到m个结果 if (targetSeq.size() == m) { totalSeq.push_back(targetSeq); return; } // 否则继续做出选择 for (size_t i = 0; i < sourceSeq.size(); i++) { // 做出选择 // 如果已经选取过第i个元素，则跳过 if (bitMap[i]) continue; targetSeq.push_back(sourceSeq[i]); bitMap[i] = true; // 递归调用 permutation(sourceSeq, m, targetSeq, totalSeq, bitMap); // 撤销选择 targetSeq.pop_back(); bitMap[i] = false; } } }; int main() { vector<int> seq = {1, 2, 3, 4, 5}; auto result = Permutation<int>().permutation(seq, 3); cout << result.size() << endl; for (int i = 0; i < result.size(); i++) { cout << '['; int j = 0; for (; j < result[i].size() - 1; j++) { cout << result[i][j] << ','; } cout << result[i][j]; cout << ']' << endl; } return 0; }

测试结果

组合

代码实现

#include <iostream> #include <vector> using namespace std; template <typename T>class Combination { public: typedef vector<T> Sequence; public: // 从序列sourceSeq中选取m个元素的组合 vector<Sequence> combination(const Sequence &sourceSeq, int m) { if (m <= 0 || m > sourceSeq.size()) return {}; vector<Sequence> totalSeq; Sequence targetSeq; combination(sourceSeq, m, 0, targetSeq, totalSeq); return totalSeq; } private: void combination(const Sequence &sourceSeq, int m, int cur, Sequence &targetSeq, vector<Sequence> &totalSeq) { if (targetSeq.size() == m) { totalSeq.push_back(targetSeq); return; } for (int i = cur; i < sourceSeq.size(); i++) { // 做出选择 targetSeq.push_back(sourceSeq[i]); // 递归调用 combination(sourceSeq, m, i + 1, targetSeq, totalSeq); // 撤销选择 targetSeq.pop_back(); } } }; int main() { vector<int> seq = {1, 2, 3, 4, 5}; auto result = Combination<int>().combination(seq, 3); cout << result.size() << endl; for (int i = 0; i < result.size(); i++) { cout << '['; int j = 0; for (; j < result[i].size() - 1; j++) { cout << result[i][j] << ','; } cout << result[i][j]; cout << ']' << endl; } return 0; }

测试结果