全排列递归实现

全排列的概念：

给定n个元素，输出所有不同的排列情况。

递归的思路：

例子：对于字符串 abcd的全排列，我们可以这样看待。
它的全排列应当是以字符串abcd中任一字符+其它字符的全排列：
就abcd这个例子，分以下情况：
a + bcd的全排列
b + acd的全排列
c + abd的全排列
d + abc的全排列

可以看到我们已经能构造出子问题了。
实现的方式就是分别将当前字符串每个位置分别与首字符作对换，然后求除首字符位置外的部分的全排列。一直这样递归下去。

上代码：

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
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<vector>
using namespace std;
static vector<vector<char>> vec;
void swap(vector<char>& arr, int a, int b) {
	char tem = arr[a];
	arr[a] = arr[b];
	arr[b] = tem;
}
// n是原始的字符串长度，k - n区间的字符是需要进行全排列的部分。
void getPermutation(vector<char>& arr, int k, int n) {
	int i, size;
	if (k == n) {
		size = vec.size();
		vec.resize(vec.size() + 1);
		size = vec.size();
		vec[size-1].resize(n);
		for (i = 0; i < n; i++) {
			vec[size - 1][i] = arr[i];
		}
		return;
	}
	for (i = k; i < n; i++) {
		swap(arr, k, i);	// 将需要进行全排列的区段中的每一字符分别与该区段的首字符交换
		getPermutation(arr, k + 1, n);
		swap(arr, k, i);	// 恢复原状
	}
}
int main() {
	int n;
	while (cin >> n) {
		vector<char> arr(n, 0);
		for (int i = 0; i < n; i++) cin >> arr[i];
		getPermutation(arr, 0, n);	//  最初是对 0 - n这一区段进行全排列
		int count = vec.size();
		int size;
		for (int i = 0; i < count; i++) {
			size = vec[i].size();
			for (int k = 0; k < size; k++) {
				cout << vec[i][k];
			}
			cout << endl;
		}
	}
	return 0;
}

复杂度分析

时间复杂度：
O(n!)
空间复杂度：
O(n!)
函数栈的最大深度应该是 n，（除main函数）。但不幸的是实际上申请销毁函数栈的次数是n!，非常可怕的开销。所以这是一个效率低下的方法。
另一方面，使用vector来保存所有的排列情况，对于有重复元素的情况是不能做到去重的，其实可以考虑用set。set的数据结构是二叉查找树，每次插入是logn的复杂度，总的时间复杂度是O(n!logn)。我选择原地爆炸。

学习完字典序方式求全排列后会将更高效的方法写上来。有条件我会做效率对比。

以上。