小红书是上海的一家基于b2c的电商，虽然没有阿里巴巴的名气但是也是一家处于快速发展的企业，这个公司对算法比较重视，一上来就要求用递归方法写
一个全排列，幸好还记得一些思路，最后还是被我写出来了，一下是当时写的代码：
#include<iostream>#include<vector>#include<map>#include<set>#include<sstream>#include<fstream>#include<cstring>#include<stack>#include<algorithm>using namespace std;vector<vector<int>>get_all_permutation(vector<int>&data, int end){vector<vector<int>>re;vector<vector<int>>tmp;if (end == 0){vector<int>temp;temp.push_back(data[end]);re.push_back(temp);return re;}re = get_all_permutation(data, end - 1);for (int i = 0; i<re.size(); i++){int count = 0;vector<int>::iterator iter;int size = re[i].size();int index = 0;while (count != size + 1){iter = re[i].begin();for (int k = 0; k < index; k++)iter++;re[i].insert(iter, data[end]);tmp.push_back(re[i]);iter = re[i].begin();for (int k = 0; k < index; k++)iter++;re[i].erase(iter);index++;count++;}}return tmp;}int main() {int num;vector<int>data;vector<vector<int>>re;int count = 1;while (count){num = 0;if (num<1){cout << 0 << endl;return 0;}for (int i = 1; i <= num; i++)data.push_back(i);re = get_all_permutation(data, num - 1);cout << '[';for (int i = 0; i<re.size(); i++){cout << '[';for (int j = 0; j<re[i].size(); j++){cout << re[i][j];if (j != re[i].size() - 1)cout << ',';}cout << ']';if (i != re.size() - 1)cout << ',';}cout << ']' << endl;count--;}return 0;}//Input: 数字 n //Output: 以二维数组的形式，输出[1,2,...,n]的全排列。 //例如：当n=3时，输出[[1,2,3], [1,3,2], ..., [3,2,1]]//标准解法：递归。
这种方法比较乱，主要思想是利用插空法，假设我们在a,b,c三个字符的情况下，我们调用函数递归调用返回b,c和c,b那么我们可以将a插入到b,c和c,b的每一位
置，那么对于b,c来说，就会有abc,bac,bca,对于c,b来说，我们就有acb,cab,cba；
但是在正常情况下,我们的输出序列为：
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
后来又写了另外一种方法：
#include<iostream>#include<string>#include<vector>#include<memory>#include<fstream>using namespace std;vector<vector<int>> get_all_permutation(vector<int>&data,int begin){vector<vector<int>>re;vector<int>tmp;if (begin == data.size()-2){//这个时候还剩两个元素tmp.push_back(data[begin]);tmp.push_back(data[begin+1]);re.push_back(tmp);//交换两个数tmp[0] = tmp[0] ^ tmp[1];tmp[1] = tmp[0] ^ tmp[1];tmp[0] = tmp[0] ^ tmp[1];re.push_back(tmp);return re;}re = get_all_permutation(data,begin+1);for (int i = 0; i < re.size(); i++)re[i].insert(re[i].begin(), data[begin]);int num = re.size();for (int i = 0; i < num; i++){//将0号下标和从1号下标开始的元素交换for (int j = 1; j < re[i].size(); j++){tmp = re[i];tmp[0] = tmp[0] + tmp[j];tmp[j] = tmp[0] - tmp[j];tmp[0] = tmp[0] - tmp[j];re.push_back(tmp);}}return re;}int main(){int num;vector<int>data;vector<vector<int>>re;while (cin>>num){if (num == 0)return 0;if (num == 1){ cout << num << endl; continue; }for (int i = 1; i <= num; i++)data.push_back(i);re = get_all_permutation(data,0);cout << '[';for (int i = 0; i < re.size();i++){cout << '[';for (int j = 0; j < re[i].size(); j++){cout << re[i][j];if (j != re[i].size() - 1)cout << ',';}cout << ']';}cout << ']' << endl;data.clear();}}
再用树的结构来写一遍(这种思想用到dfs和回溯方法)：
#include<vector>#include<memory>#include<fstream>#include<stack>using namespace std;void get_all_permutation(vector<int>&data,vector<bool>&flag,vector<int>&stk){//begin代表当前的下标int size = data.size();if (stk.size() == data.size()){cout << '[';for (int i = 0; i < stk.size(); i++){cout << stk[i];if (i != stk.size() - 1)cout << ',';}cout << ']';return;}for (int i = 0; i < size;i++){if (flag[i] != true){//可以继续访问flag[i] = true;stk.push_back(data[i]);get_all_permutation(data,flag,stk);stk.pop_back();flag[i] = false;}}}int main(){int num;vector<int>data;vector<vector<int>>re;vector<bool>flag;while (cin>>num){if (num == 0)return 0;if (num == 1){ cout << num << endl; continue; }for (int i = 0; i < num; i++)flag.push_back(false);for (int i = 1; i <= num; i++)data.push_back(i);cout << '[';int count = 0;vector<int>stack;get_all_permutation(data,flag,stack);cout << ']' << endl;data.clear();flag.clear();}}
可以用STL里面的next_permutation函数实现一遍
