next_permutaion和prev_permutation
STL中迭代器范围内的排列算法，next_permutaion和prev_permutation即是。
头文件：
#include <algorithm>函数原型：
bool next_permutation(iterator start, iterator end);next_permutation函数的返回值是布尔类型
next_permutation()函数功能是输出所有比当前排列大的排列，顺序是从小到大。
prev_permutation()函数功能是输出所有比当前排列小的排列，顺序是从大到小。
要理解next_permutation和prev_permutation，先看看什么是全排列中的“下一个全排列”，
什么是“上一个全排列”。考虑由三个字符组成的序列{
a,b,c},这个序列的全排列有6组元素，
分别是abc, acb, bac, bca, cab, cba。上面的6组元素是按照字典序排序的。
acb即是abc的下一个全排列，同样，cab是cba的上一个全排列。我们再来看下面一个例子，有如下的一个数组1 2 7 4 3 1下一个排列为：1 3 1 2 4 7那么是如何得到的呢，我们通过观察原数组可以发现，如果从末尾往前看，数字逐渐变大，
到了2时才减小的，然后我们再从后往前找第一个比2大的数字，是3，那么我们交换2和3，
再把此时3后面的所有数字转置一下即可，步骤如下：1 2 7 4 3 11 2 7 4 3 11 3 7 4 2 1 // 3 和 2交换1 3 1 2 4 7 // 交换完后 将3后面的按照升序排列 // （升序就是最小的排序，降序是最大的排序）
permutations
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3]have the following permutations:
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], and[3,2,1].
方法一：
class Solution {
public:vector<vector<int> > permute(vector<int> &num) {vector<vector<int> > V;sort(num.begin(),num.end());do{V.push_back(num);}while(next_permutation(num.begin(),num.end()));return V;}
};方法二：
class Solution {
public:vector<vector<int> > permute(vector<int> &num) {vector<vector<int>> V;permutations(V,num,0);return V;}void permutations(vector<vector<int>> &V ,vector<int> &num, int s ){if(s == num.size()-1)V.push_back(num);else{for( int i = s; i < num.size(); i++ ){swap(num[s],num[i]);permutations(V,num,s+1);swap(num[s],num[i]);}}}
};permutation-ii
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2]have the following unique permutations:
[1,1,2],[1,2,1], and[2,1,1].
方法一：
class Solution {
public:vector<vector<int> > permute(vector<int> &num) {vector<vector<int> > V;sort(num.begin(),num.end());do{V.push_back(num);}while(next_permutation(num.begin(),num.end()));return V;}
};方法二：
class Solution {
public:vector<vector<int> > permute(vector<int> &num) {vector<vector<int>> V;_permuteUnique(num,V,0);return V;}bool IsUnique(vector<int> &num,vector<vector<int> > &V){for(int i =0;i < V.size(); i++){if( num == V[i])return false;}return true;}void _permuteUnique(vector<int> &num,vector<vector<int> > &V,int s){if( s == num.size()-1 && IsUnique(num,V)){V.push_back(num);}else{for(int i = s; i < num.size(); i++){if( num[s] != num[i] ){swap(num[s],num[i]);_permuteUnique(num,V,s+1);swap(num[s],num[i]);}else_permuteUnique(num,V,s+1);}} }
};