知识储备

全排列：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

字典序：在数学中，字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法。

简单的来说就是：abc>abd 以及123>132 （这里的>是指字典序靠前）

最直观的想法，直接递归枚举

算法思想：

用一个数组ans来存储生成的排列，并在递归出口结束时输出。假设生成0，1，2三个数字组成的全排列，首先考虑第一位，第一位可能放置0到2中的一个，就有3种情况，然后后面2位再递归的生成它们的全排列。但是这样的代码执行后会发现出现，不同位置上重复出现相同数字的情况。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
int ans[100];
int len = 5;
void generate(int n)
{
	if (n == len) {
		for (int i = 0; i < len; i++)
			printf("%d", ans[i]);
		printf("\n");
		return;
	}
	for (int i = 0; i < len; i++)
	{
		ans[n] = i;
		generate(n + 1);
	}
}
int main()
{
	generate(0);
	return 0;
}

执行结果如下：

1
2
3
4
5
6
7
8
9
10
000
001
002
010
011
...
...
220
221
222

发现生成的数是有000，011，222这样重复数字的，只需要在递归前加上一个判断，判断当前数字是否使用过，使用过则跳过此次递归即可。

改进后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
#define N 100
int ans[N];
int visit[N];	//用于标记是否使用
int len = 3;
void generate(int n)
{
	if (n == len) {
		for (int i = 0; i < len; i++)printf("%d", ans[i]);
		printf("\n");
		return;
	}
	for (int i = 0; i < len; i++)
	{
		if (!visit[i]) {	//i没被标记，才可使用
			ans[n] = i;
			visit[i] = 1; //标记为使用
			generate(n + 1);
			visit[i] = 0; //回溯取消标记
		}
	}
}
int main()
{
	generate(0);
	return 0;
}

这种方式生成的全排列是按照for循环中，访问的元素顺序排列的

经典的全排列方式：递归交换元素

算法思想：

通过交换依次固定首位排放的元素，然后将剩下的元素进行递归的全排列，其实本质上和前面提到的方法是一样的，都是枚举每个位置出现的元素，但是，通过交换再回溯的方式，可以不用额外的判断当前元素之前是否已经参与排列，缺点就是全排列无序。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<cstdio>
void my_swap(int* arr, int a, int b)
{
	int tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
}
void permutation(int* arr, int curser, int end)
{
	if (curser == end) {//递归出口，输出排列数
		for (int i = 0; i <= end; i++)printf("%d", arr[i]);
		printf("\n");
		return;
	}
	/*
	先固定下标为curser的数，然后求剩下数的全排列
	curser可依次取arr[curser...end]中的值
	*/
	for (int i = curser; i <= end; i++)
	{
		my_swap(arr, i, curser);//把第i位固定在首位curser中，即与arr[curser]交换
		permutation(arr, curser + 1, end);//把交换后剩下的数进行递归全排列
		my_swap(arr, i, curser);	//避免下轮循环时，arr[curser...end]中的值发生改变
	}

}
int main()
{
	int arr[] = { 1,2,3 };
	permutation(arr, 0, 2);//输出arr中下标0->size-1的全排列
	return 0;
}

解决重复元素问题

前面提到的方法都不能解决带有重复元素时的全排列问题，即当求1，1，2这样元素全排列时，会发现结果如下：

122
122
212
221
221
212

带有重复元素的排要都输出了两次，这显然不是我们想要的

解法方法：在原有的代码基础上加个check函数进行判断，在逐个元素与首位进行交换的过程中，若发现此前已经有相同的元素与首位发生了交换，则跳过此元素的交换。

举个例子：

在求arr[ 1,2,1,3,]的全排列时，

先固定首位为1，然后求递归求213的全排列，

再通过交换，把首位置为2，然后递归求113的全排列

再通过交换，把首位置1，然后递归求213的全排列，

再通过交换，把首位置3，然后递归求211的全排列，

会发现，首位会出现两次为1的情况，而递归求213的全排列后得到的结果也一模一样，

因此若在交换时，发现已经在之前有相同元素交换到首位，则跳过这个元素的交换，

此例中，当下标i为2时，发现从i=0(cursor)到i=1(i-1)中出现过重复的元素arr[0]=1，故跳过此元素可避免重复。

详细代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
void my_swap(int* arr, int a, int b)
{
	int tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
}
bool check(int* arr, int curser, int i)
{
	for (int j = curser; j < i; j++)
		if (arr[j] == arr[i])return false;
	return true;
}
void permutation(int* arr, int curser, int end)
{
	if (curser == end) {//递归出口，输出排列数
		for (int i = 0; i <= end; i++)printf("%d", arr[i]);
		printf("\n");
		return;
	}
	for (int i = curser; i <= end; i++)
	{
		/*
			i从curser取到end，
			当[curser,i)中已经存在与arr[i]重复的元素时，跳过此轮循环
			因为已经有相同的元素固定在首位，剩余元素求全排列了，
			此时若再把i交换到curser，则剩余的数与上次交换重复元素时相同，排列结果自然就相同
		*/
		if (check(arr, curser, i)) {
			my_swap(arr, i, curser);
			permutation(arr, curser + 1, end);
			my_swap(arr, i, curser);
		}
	}
}
int main()
{
	int arr[] = { 1,2,2 };
	permutation(arr, 0, 2);//输出arr中下标0->size-1的全排列
	return 0;
}

字典序方式实现全排列

现在，考虑一下递归交换算法的时间复杂度，for循环需要循环n,每次递归进行要循环n-1此，因此时间复杂度是n * (n-1) * (n-2) * … * 1，即O(n!)，加上处理重复元素问题时，还有一个for循环的遍历，时间复杂度还是挺高的。

如果只是想得到某个排列1324的的下一个排列数1342，总不能每次都把所有排列生成一遍吧，这样效率太低了，因此接下来的这种算法可以根据当前状态生成下一个排列数，每生成一个排列数的时间复杂度是O(n)。

算法思想：

设P是1～n的一个全排列:p=p1p2……pn=p1p2……pj-1pjpj+1……pk-1pkpk+1……pn
　　1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i|pi<pi+1}
　　2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i|pi>pj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）
　　3）对换pi，pk
　　4）再将pj+1……pk-1pkpk+1……pn倒转得到排列p’=p1p2…..pj-1pjpn…..pk+1pkpk-1…..pj+1，这就是排列p的下一个排列。

上面这东西是我复制的，其证明过程感兴趣的可以看这里https://blog.csdn.net/cpfeed/article/details/7376132

在leetcode上看到这么一句评论，觉得很在理。

If idea behind an explanation is to confuse the audience by fancy mathematic stuff then congratulations, mission accomplished.

通俗的来讲算法分为3步：

1.从右往左，找到第一个顺序对(pi, pj)，pi<pj，j=i+1

2.再一次从右往左找到第一个大于pi的数p，交换pi和pk的值

3.把pi后的数逆序

以146532为例

从右往左，第一个逆序对，46

再一次从右往左，找到第一个大于4的数，为5

交换4和5，得到156432

把交换后的5，之后的数全部逆序，得到152346

162346即为下一个排列

然后就是照着思路把实现代码敲出来就可以了

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
void my_swap(int* arr, int a, int b)
{
	int tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
}
//输出当前arr的下一个全排列
bool next_permu(int* arr, int size)
{
	for (int i = size - 2; i >= 0; i--)
	{
		if (arr[i] < arr[i + 1]) {
			int j;
			//此时i-1后的数组已是降序，故从后往前
			for (j = size - 1; j > i && arr[j] <= arr[i]; j--);
			my_swap(arr, i, j);	//最大字典序时，i=j,故不需要额外判断for循环退出的条件
			for (int low = i+1, high = size - 1; low < high; low++, high--)
				my_swap(arr, low, high);
			return true;
		}
	}
	return false;
}

int main()
{
	int arr[] = { 1,2,2,2 ,4 };
	int size = 4;
	//先输出123，最初的排列
	for (int i = 0; i < size; i++)printf("%d", arr[i]); printf("\n");
	while (next_permu(arr, size)) {
		for (int i = 0; i < size; i++)printf("%d", arr[i]);
		printf("\n");
	}
	return 0;
}