排列问题方法总结（递归+迭代）

递归

一、逐步生成结果法（无序）

#include<iostream>  
#include<vector>  
#include<string>
#include<algorithm>using namespace std;vector<string> GetChild(int n,int curIndex){vector<string> now;vector<string> cur;if (curIndex == 1) {  now.push_back("1");cur=now;return cur;}cur=GetChild(n, curIndex - 1);for (string temp : cur) {now.push_back(temp + to_string(curIndex));now.push_back(to_string(curIndex) + temp);for (int j = 1; j < temp.size(); j++) {now.push_back(temp.substr(0, j) + to_string(curIndex) + temp.substr(j));}}cur = now;return cur;
}int main(void) {int n,k;cin >> n>>k;// 获取子集vector<string>ans = GetChild(n,n); // 存放子集的数组//排序sort(ans.begin(), ans.end());// 输出子集个数int n_ = ans.size();cout << "子集个数：" << n_ << endl;// 输出子集  for (auto sub_set : ans) {cout << sub_set << endl;}cout<<endl;// 输出第k个子集cout << ans[k - 1];return 0;
}

这个代码主要就是讲的是逐步生成结果，然后它主要就是利用了一个递归的思想。

首先就是先假设我求出来了前 n -1 个数的排列，然后我作为老板我只需要去 排列 第 n 个数。它的排法一共有三种，首先就是可以把这个数插在这个排列的前面，也可以插在排列的后面。除此之外也可以插在这个排列的中间的任何一个空里面。

总的来说他主要就是将这个新的数插到一切可以插的空里面，然后记录即可。

对于递归出口，我们要设一个变量，用来代表我当前是对于第几个元素进行操作，当达到第一个元素时，那么就新建一个数组，然后将这个第一个元素放进去，代表我是一个数的排列，就是它本身。

但是这种方法求出来的排列并不是有序的，我们在最后输出结果的时候要记得对这个排列进行排序。（后面有已序的求法）

递归的思想前面也说过，它主要就是一种老板思维，就是我不需要去考虑一些细节上的东西，相当于把一些重复性的工作让员工去做，然后我只需要进行最后一步，或者说是特定的一步即可。然后注意初始条件。

---

二、基于交换的递归方法（交换完排序则是有序）

#include<iostream>  
#include<vector>  
#include<string>  
#include<algorithm>  using namespace std;vector<string> ans;void GetChild(string s, int n, int curIndex) {cout << string(curIndex, ' ') << "+-- " << s << endl; // 打印当前状态  if (curIndex == n) {ans.push_back(s);cout << string(curIndex, ' ') << "|   Found permutation: " << s << endl; // 指示找到的排列  return; // 退出递归  }for (int i = curIndex; i < n; i++) {swap(s[i], s[curIndex]);sort(s.begin() + curIndex + 1, s.end()); // 交换后，将curIndex之后的元素排序(保证字典序)GetChild(s, n, curIndex + 1);swap(s[i], s[curIndex]); // 还原交换  }cout << string(curIndex, ' ') << "+-- Exiting depth " << curIndex << ": " << s << endl; // 打印退出当前状态  }
int main(void) {int n;cin >> n;// 初始化字符串并排序  string s = "";for (int i = 1; i <= n; i++) {s += to_string(i);}GetChild(s, n, 0); // 生成所有排列  // 输出排列个数  int n_ = ans.size();cout << "排列个数：" << n_ << endl;// 输出所有排列  for (const auto& sub_set : ans) {cout << sub_set << endl;}return 0;
}

CurIndex 指的是当前元素的下标。递归操作时先交换i处和当前下标元素的位置，然后对后面的元素进行一个升序排序，就是字典序。

然后递归的调用这个函数，最后再还原交换。

当我的CurIndex 等于 n 的时候，相当于我从第一个元素遍历到第二个元素，然后 存入s 。（s在交换的过程中被改变，初始化为升序排列）

---

三、逐个交换大法（有序）

#include<iostream>  
#include<vector>  
#include<string>  
#include<algorithm>  using namespace std;vector<string> ans;
int cnt = 0;
int flag = 0;int Mcount(string s, char c) {int count = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == c) {count++;}}return count;
}void GetChild(string s, string arr,int k) {if (flag == 1) {return;}if (s.size() == arr.size()) {cnt++;ans.push_back(s);if (cnt == k) {flag = 1;    }}for (int i = 0; i < arr.size(); i++) {char c = arr[i];if (Mcount(s,c) < Mcount(arr,c)) {GetChild(s + c, arr, k);}if (flag == 1) {return;}}
}
int main(void) {int n,k;cin >> n>>k;// 初始化字符串并排序  string s = "";for (int i = 1; i <= n; i++) {s += to_string(i);}GetChild("", s, k); // 生成所有排列  // 输出排列个数  int n_ = ans.size();cout << "排列个数：" << n_ << endl;// 输出所有排列  for (const auto& sub_set : ans) {cout << sub_set << endl;}cout << endl;cout<<ans[k-1]<<endl;return 0;
}

Mcount参数是用来记录当前元素在字符串中的个数。

Getchild 函数里面进行递归操作。

递归出口就是 s 的大小等于数组大小，然后记录这个数字里面字符串的数目，当它等于 k 的时候，我们就让递归函数退出。

然后基本的递归操作就是记录当前的字符，然后判断在当前排列和数组中该字符的个数。如果说当前字符串中，该字符个数小于数组中的话，就把当前字符加到我的当前s的后面，然后递归的去求。

这个是一个有序的递归方法。主要是因为对于元素的添加是有序的。

递归退出主要是利用一个 flag 标志，当满足条件的时候改变这个标志，然后在递归函数的出口前判断这个标志。

---

迭代：

逐步生成迭代大法：

#include<iostream>  
#include<vector>  
#include<string>
#include<algorithm>using namespace std;vector<string> GetChild(int n) {vector<string> cur;cur.push_back("1");for (int i = 2; i <= n; i++) {vector<string> now;for (string temp : cur) {now.push_back(temp + to_string(i));now.push_back(to_string(i) + temp);for (int j = 1; j < temp.size(); j++) {now.push_back(temp.substr(0, j) + to_string(i) + temp.substr(j));}}cur = now;}return cur;
}int main(void) {int n,k;cin >> n>>k;// 获取子集vector<string>ans = GetChild(n); // 存放子集的数组//排序sort(ans.begin(), ans.end());// 输出子集个数int n_ = ans.size();cout << "子集个数：" << n_ << endl;// 输出子集  for (auto sub_set : ans) {cout << sub_set << endl;}cout<<endl;// 输出第k个子集cout << ans[k - 1];return 0;
}

这个逐步生成的迭代大法其实和上面那个递归的逐步生成方法类似，它的思想也是一致的。首先我是建立一个字符串数组，然后先放入第一个元素，也就是1。

然后紧接着我遍历所有元素，对于当前的元素的话，它有三种可能的放置方式，首先是放在原有排列的前面，还有一种是放在排列后面，或者是插在这个排列的中间。总而言之它就是放在所有能放的位置.

---

利用排列性质的迭代算法：

#include<iostream>  
#include<vector>  
#include<algorithm>using namespace std;vector<vector<int>> GetChild(int n) {int row = n;vector<vector<int>> cur;for (int i = 0; i < row; i++) {vector<int> temp(n, 0);temp[i] = 1;cur.push_back(temp);}for (int i = 2; i <= n; i++) {vector<vector<int>> now;vector<int> temp;for (int j = 0; j < cur.size(); j++) {for (int k = 0; k < n; k++) {temp = cur[j];if (temp[k] == 0) {temp[k] = i;now.push_back(temp);}}}cur = now;}return cur;
}int main(void) {int n,k;cin >> n>>k;// 获取子集vector<vector<int>>ans = GetChild(n); // 存放子集的数组//排序sort(ans.begin(), ans.end());// 输出子集个数int n_ = ans.size();cout << "子集个数：" << n_ << endl;// 输出子集  for (auto sub_set : ans) {cout << "{ ";for (auto elem : sub_set) {cout << elem << " ";}cout << "}" << endl;}// 输出第k个子集for (auto elem : ans[k - 1]) {cout << elem;}return 0;
}

这个迭代法的主要思路就是按照顺序把对应的元素排在能排在第一个位置。

首先就是我要初始化一个二维数组，这个二维数组用矩阵的思维去看的话，它应当是一个单位矩阵，也就是在它主对角线上面一个元素都是1，然后就是这个矩阵里的1，分别代表1这个元素在第一个到第 n 个位置上的情况。

然后对于每一个其他元素，遍历当前的这个二维数组。然后对于每一个一维数组来说，我的第二个元素他能放在第一个位置是哪个？然后我将它放在这个位置上，然后依次类推第三个元素，它能放的第一个位置就是没有元素占领的位置，然后再把这个新的元素给它保存下来，最终就得到我们的结果。

这个方法其实也不是一个有序的，我们最后也要对它进行排序，然后这个方法其实是利用到排列的每个元素都有可能在每个位置上这样一种思想。