题目描述：
排列与组合是常用的数学方法。
先给一个正整数 ( 1 < = n < = 10 )
例如n＝3，所有组合,并且按字典序输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
本文将从以下三种方法介绍本题
1.首先，类似于合法括号，本题可以先选定一个数，对于下一个数，选择放在当前数的左边，右边或中间，生成的下一个集合继续进行下一次迭代，直到遍历完所有情况。
2.考虑到第一种方法需要进行频繁的字符串操作，所以第二种方法是先选定一个字符当前缀，然后逐步增加前缀的长度。如果前缀长度等于输入的长度，就得到了一组解。需要注意的是本方法用到递归，需要处理好平行状态。（这种方法的好处还有不需要那麽多空间来记录）
3.进一步考虑，类似于DFS，本题还可以用递归+回溯。
逐步生成法：
#include<iostream> #include<list> #include<string> #include<algorithm> using namespace std; list<string> getPermutation(string A){ list<string> res; string st(1,A.at(0)); res.push_back(st); int len = A.length(); for(int i = 1; i < len; i++){ list<string> res_new; char c = A.at(i); for(list<string>::iterator it = res.begin(); it != res.end(); it++){ string str = *it; string s_new = *it+c;// 加在后面 res_new.push_back(s_new); s_new = c+*it;//加在前面 res_new.push_back(s_new); // 加在中间 for(int j = 1; j < str.length(); j++){ s_new = str.substr(0,j) + c + str.substr(j); res_new.push_back(s_new); } } res = res_new; } return res; } int main(){ string s; cin >> s; list<string> res = getPermutation(s); for(list<string>::iterator it = res.begin(); it != res.end(); it++){ cout << *it << " "; } cout << endl; return 0; }
前缀法：
#include<iostream> #include<string> #include<algorithm> using namespace std; int k, sum = 0; void getPermutation(string perfix, string arr){ if(perfix.length() == arr.length()){ sum++; if(sum == k){ cout << perfix << endl; exit(1); } } for(int i = 0; i < arr.length(); i++){ char c = arr[i]; if(count(perfix.begin(),perfix.end(),c) < count(arr.begin(),arr.end(),c)) getPermutation(perfix+c,arr); } } int main(){ string s; cin >> s >> k; getPermutation("", s); return 0; }
回溯法：
#include<iostream> #include<string> #include<list> #include<algorithm> using namespace std; list<string> res; void getPermutationCore(string arr, int k){ if(k == arr.length()){ res.push_back(arr); } for(int i = k; i < arr.length(); i++){ swap(arr[k], arr[i]); // 把k后面的每个字符放到k的位置上 getPermutationCore(arr, k+1); // 放好之后再放下一个元素 swap(arr[k], arr[i]); // 回溯 } } int main(){ string s; cin >> s; getPermutationCore(s,0); res.sort(); for(list<string>::iterator it = res.begin(); it != res.end(); it++) cout << *it << " "; cout << endl; return 0; }
