C++ STL求全排列和组合

本文主要是介绍C++ STL求全排列和组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C++11 STL内置了求全排列的模板函数next_permutation和prev_permutation，属于<algorithm>头文件和std命名空间，使用非常方便。例如：

vector<int> A{1,2,3,4,5};
while (next_permutation(A.begin(),A.end())
{cout<<A[0]<<A[1]<<A[2]<<A[3]<<A[4]<<endl;
}

其本质上是通过交换元素实现的，返回值为true则表示排列尚未穷尽。所以输入数组初始状态应按升序排列。

---

但是组合就没有这种方便的函数可用了。
例如C(n,m)，在m较小时可以手写循环，以C(5,3)为例：

    vector<int> A{1,2,3,4,5};for (int i = 0; i < A.size() - 2; ++i)for (int j = i + 1; j < A.size() - 1; ++j)for (int k = j + 1; k < A.size(); ++k){cout<<A[i]<<A[j]<<A[k]<<endl;}

但是这样需要写m个循环函数，我们改成递归形式，再改成模板函数，这样就可以同时支持vector<int>和string了：

template <typename T>
void combine_inner(T &data, int start, int n, int m, int depth, T temp,vector<T> &result)
{if (depth == m - 1){//最内层循环 将temp加入resultfor (int i = start; i < n - (m - depth - 1); ++i){temp[depth] = data[i];result.push_back(temp);}}elsefor (int i = start; i < n - (m - depth - 1);++i){temp[depth] = data[i];//每层输出一个元素combine_inner(data,i + 1, n, m, depth+1,temp,result);}
}//T可以调入vector<int>, string等，需要支持下标[]操作及size()函数
template <typename T>
vector<T> combine(T &data,int m)
{if (m <= 0)return{};int depth = 0;vector<T> result;T temp(m,0);combine_inner(data,0, data.size(), m, depth,temp,result);return result;
}

调用时只需要这样：

    string s("ABCDEF");vector<string> result = combine(s, 3);

很方便吧。时间复杂度O(C(n,m))，空间复杂度O(1)。

这篇关于C++ STL求全排列和组合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---