全排列的实现-- 递归
中心思想:
设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}.
Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列。
（1）当n=1时，Perm(R)=(r),其中r是集合R中唯一的元素；
（2）当n>1时，Perm(R)可由(r1)+Perm(R1),(r2)+Perm(R2),…,(rn)+Perm(Rn)构成。
那么具体程序要怎么实现呢?我们来个实际的例子,假设有一数列1,2,3,4
那么1,2,3,4的全排列
perm({1,2,3,4})=1perm({2,3,4})+2perm({1,3,4})+3perm({1,2,4})+4perm(1,2,3)
那么我们只要将每个数,与第一个数交换不就可以得到下一个序列了。
比如{1,2,3,4}第一个与第二个数交换,那么不就得到2 {1,3,4}了。
// 输出n个整数的全排列 #include<iostream> using namespace std; void swap(int & a, int & b){ int tmp; tmp = a; a = b; b = tmp; } void perm(int list[], int low, int high) { if (low == high) //当low == high时，此时list就是其中一个排列,所以输出 { for (int i = 0; i <= high; i++){ cout << list[i]; } cout << endl; } else { for (int i = low; i <= high; i++) // i 从 low 变化到 high,每个元素与第一个元素交换 { swap(list[low], list[i]); perm(list, low + 1, high); // 交换后，得到子序列，用函数perm得到子序列的全排列 swap(list[low], list[i]); // z最后将元素交换回来，复原，然后为下一步交换另一个元素做准备 } } } int main(){ int list[10] = {0,1,2,3,4,5,6,7,8,9}; perm(list, 0, 2); return 0; }
Leetcode 46 Permutations
Given a collection of distinct numbers, return all possible permutations.
For example,[1,2,3] have the following permutations:
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
/* 比如 abcde的排列 a-bcde b-acde c-abde d-abce e-abcd cb-ade db-cae.... */ class Solution { public: void perms(vector<int> nums, int low, int high, vector<vector<int>>& res){ if (low == high){ res.push_back(nums); // 此时为base，这时已经到了排列的最后一个字符，即已经完成了一个全排列，只需将这个排列存入结果 } else{ for(int i = low; i <= high; i++){ int tmp = nums[i]; nums[i] = nums[low]; nums[low] = tmp; perms(nums, low + 1, high, res); tmp = nums[i]; nums[i] = nums[low]; nums[low] = tmp; } } } vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; if (nums.size() == 0) return res; int len = nums.size(); perms(nums, 0, len - 1, res); return res; } };
STL模板实现
在C++的模板中，有一对专门用于实现数字或字符全排列的模板：next_permutation(_BIter, _BIter)和prev_permutation(_BIter, _BIter)。前者实现向后排列，后者实现向前排列，即前者在原顺序上依次产生较大的排列，后者则相反。
举个例子：假设需要产生以“354”为基础的全排列，使用next_permutation(_BIter, _BIter)，则下一个排列为“435”，而使用prev_permutation(_BIter, _BIter)，则下一个排列为“345”。
字符串的所有组合：
思路：假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个
字符中选取m-1个字符；二是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。
递归终止条件：1、所需要的剩余字符的数量为0，完成递归，输出当前字符数组。2、已到达字符串末尾，已不可能完成任务，需要结束递归
//string:要处理的字符指针 //number:表示倒数第number个字符 //result:存储已选的字符 void Combination(char* string, int number, vector<char>& result) { if(number == 0) //终止条件1 { vector<char>::iterator iter = result.begin(); for(; iter < result.end(); ++ iter) printf("%c", *iter); printf(" "); return; } if(*string == ' ') //终止条件2 return; result.push_back(*string); //保存这个字符 Combination(string + 1, number - 1, result); //递归处理下一个字符，作为倒数第number-1个 result.pop_back(); //弹出这个字符，不保存着个字符 Combination(string + 1, number, result); //处理下一个字符，作为倒数第number个 } void Combination(char* string) { if(string == NULL) return; int length = strlen(string); vector<char> result; for(int i = 1; i <= length; ++ i) { Combination(string, i, result); } } 由于组合可以是1个字符的组合，2个字符的字符……一直到n个字符的组合，因此在函数void Combination(char* string)，
我们需要一个for循环。另外，我们一个vector来存放选择放进组合里的字符。
延伸扩展
leetcode 47
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]