全排列（LeetCode 46）
1.问题描述
给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以按任意顺序返回答案。
数组的全排列可用于求解八皇后问题，具体参见：全排列解决八皇后问题。与此同时，全排列经常会出现在面试和笔试环节，如求字符串的全排列。
之所以拿它作为考题，因为难度适中，既可以递归实现，又能进一步考察非递归的实现，便于区分考生水平。所以，掌握它很重要。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]示例 3：
输入：nums = [1]
输出：[[1]]2.难度等级
Medium。
3.热门指数
★★★★☆
出题公司：腾讯
4.解题思路
4.1 递归
思路
全排列表示把集合所有元素按照一定顺序排列起来，使用 P(n, n) = n! 表示n个元素全排列的个数。P(n, n)中的第一个n表示元素的个数，第二个n表示取多少个元素进行排列。
给定一个n个元素数组，其全排列的过程可以描述如下： （1）任意取一个元素放在第一个位置，则有n种选择； （2）再剩下的n-1个元素中再取一个元素放在第二个位置则有n-1种选择，此时可以看做对n-1个元素进行全排列； （3）重复第二步，直到对最后一个元素进行全排列，即最后一个元素放在最后一个位置，全排列结束。
以数组 {1,2,3} 为例，其全排列的过程如下： （1）1 后面跟（2,3）的全排列。 （2）2 后面跟（1,3）的全排列。 （3）3 后面跟（2,1）的全排列。
图示如下：
优缺点
由于递归将问题逐级分解，因此相对比较容易理解。但需要消耗大量的栈空间，如果函数栈空间不够，那么就运行不下去了，而且函数调用开销也比较大。
具体实现
#include <iostream>
using namespace std;
int sum=0; //全排列个数
// 打印数组内容
void print(int array[],int len){
printf("{");
for(int i=0; i<len; i++) {
cout<<array[i]<<" ";
}
printf("}\n");
}
// 实现两数交换
void swap(int* o,int i,int j){
int tmp = o[i];
o[i] = o[j];
o[j] = tmp;
}
// 递归实现数组全排列并打印
void permute(int array[], int len, int index) {
if(index==len){//全排列结束
++sum;
print(array,len);
} else {
for(int i=index; i<len; ++i){
// 将第i个元素交换至当前index下标处
swap(array,index,i);
// 以递归的方式对剩下元素进行全排列
permute(array, len, index+1);
// 将第i个元素交换回原处
swap(array,index,i);
}
}
}
int main(){
int array[3]={1,2,3};
permute(array,3,0);
cout<<"sum:"<<sum<<endl;
}注意： 循环将数组中所有元素与第一个元素交换时，再对子数组进行全排列后，需要将第一个元素交换回来，以供下一个元素与第一个元素交换。
运行结果如下：
数组有重复元素
还是以数组 {1,2,3} 为例，如果数组中有重复的元素，变成了{1,2,2}，那么它的全排列就不能完全按照上面的方法求解，需要稍作改动。
因为全排列是将不同元素依次换到当前位置后，再对后面的元素全排列。如果将重复的元素多次换到当前位置的话，那么就会出现相同的排列。为了避免，我们禁止将相同元素多次换到当前位置即可。
例如，对{1，2，2}，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。
这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复数字交换。
修改后的代码如下：
// 是否交换
bool isSwap(int array[],int len,int index){
for(int i=index+1; i<len; ++i) {
if(array[index]==array[i])
return false;
}
return true;
}
// 递归实现有重复元素的数组全排列
void permute(int array[],int len,int index){
if(index==len){//全排列结束
++sum;
print(array,len);
} else {
for(int i=index; i<len; ++i) {
// 新增判断是否交换
if(isSwap(array,len,i)) {
// 将第i个元素交换至当前index下标处
swap(array, index, i);
// 以递归方式对剩下元素进行全排列
permute(array,len,index+1);
// 将第i个元素交换回原处
swap(array, index, i);
}
}
}
}实验结果：
4.2 字典序
思路
通过字典序可以非递归实现全排列。
所谓字典序就是按照元素大小对排列进行排序。比如 {1,2,3} 和 {1,3,2}，因为前一个排列的第二数 2 小于后一个排列的第二数 3，所以前一个排列排在前面。
字典序生成全排列的思想是：先从最小的排序开始，依次寻找字典序中下一个排列。
寻找字典序中下一个排列的关键就在于寻找「交换点」和「交换数」。
我们将这种方法分为四步解决，以 nums[3] = {1, 2, 3} 为例。
第一步：从右向左依次比较相邻的两个数，找到第一个比右边小的数。
因为 2 小于 3，所以 2 为交换点。
第二步：从右向左找到第一个比交换点大的数。
因为 3 比 2 大，所以 3 为交换数。
第三步：「交换点」和「交换数」交换。
得 {1, 3, 2}。
第四步：反转「交换点」后的数。
得下一个排列为 {1, 3, 2}。
重复上面的步骤，将得到有序的全排列。
{1, 2, 3} < {1, 3, 2} < {2, 1, 3} < {2, 1, 3} < {2, 3, 1} < {3, 1, 2} < {3, 2, 1}总的来说字典序生成全排列的步骤是：先排序，再由后向前找第一个交换点，然后由后向前找第一个比交换点大的数与交换点交换，最后反转交换点后的所有数。
这里之所以从后向前寻找，因为可以提高效率。交换点后面的数一定递减，所以只需要从后向前找第一个大于替换点的数就行了。最后反转交换点后的所有数，让交换点后的数变成字典序最小的排列。
优缺点
优点：
（1）使用迭代的方式，避免了递归实现的函数栈空间的大量消耗和函数调用的时间开销。 （2）无需考虑数组中出现的重复元素。
缺点：
（1）对数组的排序，增加了时间开销。其实这个可以优化，后面再说。 （2）每次寻找下一个排列时都要对替换点后的元素进行反转，这也增加了时间开销。
具体实现
#include <iostream>
using namespace std;
int sum = 0;
// 打印数组内容
void print(int array[], int len) {
printf("{ ");
for (int i = 0; i < len; ++i) {
cout << array[i] << " ";
}
printf("}\n");
}
// 实现两数交换
void swap(int* o, int i, int j) {
int tmp = o[i];
o[i] = o[j];
o[j] = tmp;
}
// 实现数组颠倒
void reverse(int array[], int s, int e) {
while (s < e) {
swap(array, s, e);
++s, --e;
}
}
// 快排比较函数
// 如果小于0，a 排在 b 前面
int compare(const void* a, const void* b) {
return *(int*)(a)-*(int*)(b);
}
// 字典序实现数组全排列并打印
void permute(int array[], int len) {
// 快速排序
qsort(array, len, sizeof(array[0]), compare);
sum++;
print(array, len);
while (true) {
int pos = -1;
// 从后往前寻找第一个替换点
for (int i = len - 2; i >= 0; i--)
if (array[i] < array[i + 1]) {
pos = i;
break;
}
// 排列结束
if (pos == -1) return;
// 从后向前寻找第一个大于替换点所在元素
int subsIndex = -1;
for (int i = len - 1; i > pos; i--) {
if (array[i] > array[pos]) {
subsIndex = i;
break;
}
}
// 交换
swap(array, pos, subsIndex);
// 颠倒
reverse(array, pos + 1, len - 1);
sum++;
print(array, len);
}
}
int main() {
int A[] = { 1,3,2 };
permute(A, 3);
cout << "sum:" << sum << endl;
}运行输出：
{ 1 2 3 }
{ 1 3 2 }
{ 2 1 3 }
{ 2 3 1 }
{ 3 1 2 }
{ 3 2 1 }
sum:6对于有重复元素的数组进行全排列，同样有效。
使用字典序输出集合的全排列需要注意，因为字典序涉及两个排列之间的比较，对于元素集合不方便比较的情况，可以将它们在数组中的索引作为元素，按照字典序生成索引的全排列，然后按照索引输出对应集合元素的排列。这也就省去了对数组进行排序。