文章包含全排列问题、包含重复元素的全排列问题、以及它们的递归和非递归实现、还有如何寻找下一个排列。
二、文章内容 1、全排列问题（递归解法）描述
给定一个数组nums，要求给出所有排列情况。
例子：nums = {1，2，3}，返回结果为
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
思路
对于以上nums = {1，2，3}的例子，我们对全排列的情况做一个分类：
①以1开头，后面跟着{2，3}的全排列
②以2开头，后面跟着{1，3}的全排列
③以3开头，后面跟着{1，2}的全排列
而对于{2，3}、{1，3}、{1，2}，我们又可以重复使用以上的思路，下面以{2，3}为例分析：
①以2开头，后面跟着{3}的全排列
②以3开头，后面跟着{2}的全排列
而对于{2}、{3}这些只有一个数的集合，它们的全排列就是它们本身。这也就是递归的终止条件。
以上的思路，用代码按如下方式实现：
对于一个有n个元素的数组a，假设其n个元素分别为a[n-1]。
第一步：
将其分成两个部分，第一个元素a[0]和后面其他元素，全排列表示以a[0]为首的所有排列，等于a[0]加上后面部分的全排列
第二步：
使用a[0]和后面的a[1]交换，同样，得到了以a[1]为首的所有全排列。
第三步：
交换回原来的序列，然后再交换a[0]和a[2]。这样能得到以a[2]为首的所有排列，然后再交换回初始状态
第四步：
按上面的交换--求排列--再交换回来的流程分别求出以a[3]-a[n-1]为首的所有排列。
这样就得到了所有的排列情况。
注意：对后面部分的排列情况调用递归实现，返回条件是当后面部分只有一个元素的时候。
实现：
void get_permute(vector<int>& nums, int pos, vector<vector<int>>& result) {
if (nums.size() == pos) {
result.push_back(nums);
return;
}
for (int i = pos; i < nums.size(); i++) {
swap(nums[pos], nums[i]);
get_permute(nums,pos+1,result);
swap(nums[i], nums[pos]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
get_permute(nums,0,result);
return result;
}
//这是测试用例
int main()
{
vector<int> v = {1,1,3};
auto result = permute(v);
for (auto i : result) {
for (auto j : i)
cout << j;
cout << endl;
}
system("pause");
return 0;
}