参考网址：http://blog.csdn.net/lemon_tree12138/article/details/50986990 http://blog.csdn.net/morewindows/article/details/7370155
求a1,a2,..,an全排列为：
｛ a1, (a2,...,an)的全排列；a2, (a1,a3,...,an)的全排列；a3, (a1,a2,a4,...,an)的全排列 ｝
// a1, a2, a3, a4 // 0到num.size()-1的全排列 // 出口：index等于num.size()时说明完成了一个排列 // 两个swap的效果类似于，在首层递归的for循环中， // 保证在for循环开始与结束，num数组不改变，为原始顺序a1, a2, a3, a4 // 那么首层递归中每次的交换为 a1,a2,a3,a4; a2,a1,a3,a4; a3,a2,a1,a4; a4,a2,a3,a1; // 输出不按字典序 void permutation_normal( vector< int >& num, int index ) //num为引用类型 { if( index == num.size() ) //说明排到最后一位了 { for( int i = 0; i < num.size(); i++ ) { cout << num[i] << " "; } cout << endl; return; } for( int i = index; i < num.size(); i++ ) { swap( num[i], num[index] ); permutation_normal( num, index+1 ); // num[index]不变 swap( num[index], num[i] ); // 用于对之前交换过的数据进行还原 } } // a1, a2, a3, a4（ 已排序 ） // 0到num.size()-1的全排列 // 出口：index等于num.size()时说明完成了一个排列 // 首层递归中每次的交换为: // a1,a2,a3,a4(a1<->a1); a2,a1,a3,a4(a1<->a2); a3,a1,a2,a4(a3<->a2); a4,a1,a2,a4(a4<->a3); // 输出按字典序 void permutation_seq( vector< int > num, int index ) { if( index == num.size() ) //说明排到最后一位了 { for( int i = 0; i < num.size(); i++ ) { cout << num[i] << " "; } cout << endl; return; } for( int i = index; i < num.size(); i++ ) { swap( num[i], num[index] ); permutation_seq( num, index+1 ); } } //当有重复数字时 void permutation_multi_seq( vector< int > num, int index ) { if( index == num.size() ) //说明排到最后一位了 { for( int i = 0; i < num.size(); i++ ) { cout << num[i] << " "; } cout << endl; return; } for( int i = index; i < num.size(); i++ ) { int flag = 0; /* //检查，如果num[i]这个元素与i之后某元素相同，这次就不交换num[i] for( int j = i+1; j < num.size(); j++ ) { if( num[j] == num[i] ) { flag = 1; break; } } */ //检查，如果num[i]这个元素在之前被交换过，这次就不交换num[i] //下标index~i-1都是被交换过的 //这样检查可以保证顺序 for( int j = index; j < i ; j++ ) { if( num[j] == num[i] ) { flag = 1; break; } } if( flag ) { continue; } swap( num[i], num[index] ); permutation_multi_seq( num, index+1 ); } } int main() { vector< vector<int> >res; vector<int> vec; vec.push_back(1); vec.push_back(2); vec.push_back(2); vec.push_back(3); //vec.push_back(3); //permutation_normal( vec, 0 ); //permutation_seq( vec, 0 ); permutation_multi_seq( vec, 0 ); return 0; ｝
1. 求数列的全排列，for循环里可以先swap，递归下去，返回后再swap
1.1 递归函数里传str的引用的话，一定要有两次swap才行。一次swap是错误的。
1.2 递归函数里传的str的值的话，一次swap即可，两次swap也对。
2. 另外要求按字典序输出的话有两种办法：
2.1， 先求出所有全排列，放入了vector，对结果排序即可
2.2， 在递归函数里就按字典序先后求出各个排列，即按字典序push_back进ret。
2.2方法步骤为：先对给定str排序，递归函数里传值， 然后在for循环中只有一个swap，然后递归下去，递归返回后不swap。
下一个字典序排列
21543，
1. （找到第一个升序A[I]<A[I+1]位置，for循环从右到左即可）从左到右，找到最后一个可以增大的数（位置 i, 即1），判断一个数是否可以增大：它右面是否有比它大的数。
2. （i后面，最后一个比A[I]大的位置，for循环从右到左即可）最后一个可以增大的数，增大到多少？ 增大到它右边 比它大的数中，最小的那个（位置 j, 即3）。
3. 交换找到的这两个数（ 得到23541 ）
4. 第一步的时候，i 是最后一个升序的位置，i+1及其之后都是降序，因此要将 [ i+1, n )逆序。
组合：用递归
不重复的时候，按位置，要还是不要，分别递归下去。
重复的时候，可以设置一个标记数组，标记i位置之前各个位置，是否加入到了待输出的串中。