next_permutation、prev_permutation以及is_permutation使用

next_permutationprev_permutationis_permutation next_permutation、prev_permutation以及is_permutation均为全排列相关的函数，调用时需要加入头文件#include <algorithm>

next_permutation

next_permutation的函数原型：

//default template <class BidirectionalIterator> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last); //custom template <class BidirectionalIterator, class Compare> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);

next就是下一个的意思，其中文直译过来就是下一个全排列，因此在使用next_permutation函数的时候切记要对全排列的对象进行升序排列，不然结果只会出现比当前排列大的排列，依据ASCII计算。 next_permutation(a, b)表示只对[a, b)区间的数据进行全排列，其余位置不变化

#include <iostream> #include <algorithm> #include <vector> using namespace std; #define SORT int main() { vector<int> V = {3, 2, 1 }; #ifdef SORT sort(V.begin(), V.end());//sort #endif do { for (int i = 0; i < V.size(); i++) { cout << V[i] << " "; } cout << endl; } while (next_permutation(V.begin(), V.end())); return 0; } //result /* #define SORT 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 */ /* 没有进行sort排序 3 2 1 */

prev_permutation

prev_permutation和next_permutation功能一样，唯一的区别是next_permutation下一个全排列，而prev_permutation是上一个全排列，所以运用prev_permutation的时候必须降序排列，不然只会出现比结果小的排列

#include <iostream> #include <algorithm> #include <vector> using namespace std; //#define SORT #define RSORT int main() { vector<int> V = {3, 4, 2, 1}; #ifdef SORT sort(V.begin(), V.end()); #else sort(V.rbegin(), V.rend()); #endif do { for (int i = 0; i < V.size(); i++) { cout << V[i] << " "; } cout << endl; } while (prev_permutation(V.begin() + 1, V.end() - 1)); return 0; } //result /* #define RSORT 4 3 2 1 4 2 3 1 */ /* #define RSORT 1 2 3 4 */

is_permutation

template <class ForwardIterator1, class ForwardIterator2> bool is_permutation (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> bool is_permutation (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate pred);

is_permutation用来判断两个全排列是否相等，哪怕顺序不同，只要元素一样就返回true

#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { vector<int> V1 = { 3, 4, 2, 1 }; vector<int> V2 = { 1, 3, 2, 4 }; vector<int> V3 = { 1, 3, 2, 4, 1}; vector<float> V4 = { 1.0, 3.0, 2.0, 4.0 }; vector<float> V5 = { 1.0000001, 3.0, 2.0, 4.0 }; if (is_permutation(V1.begin(), V1.end(), V2.begin())) { cout << "V1 and V2 is equal" << endl; } if (is_permutation(V1.begin(), V1.end(), V3.begin())) { cout << "V1 and V3 is equal" << endl; } if (is_permutation(V1.begin(), V1.end(), V4.begin())) { cout << "V1 and V4 is equal" << endl; } if (is_permutation(V1.begin(), V1.end(), V5.begin())) { cout << "V1 and V5 is equal" << endl; } return 0; } //result /* V1 and V2 is equal V1 and V3 is equal V1 and V4 is equal */

is_permutation单纯的比较值的大小，但是需要注意的是序列1重复的必须在序列2中展现，也就是count sequence1[i] <= count sequence2[i]。