全排列非递归实现

上次写了全排列的递归实现，简单分析了下时间和空间复杂度。元素个数比较多的时候递归实现的开销导致它几乎没有实用性了吧。学习过一些前辈总结的非递归实现后，觉得有必要把它记录下来。这里尽量讲清楚些，也算是对自己文字表达能力的训练吧。

全排列概念：

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

非递归原理

找到全排列中字典序最小的一个排列，然后找到字典序只比当前排列大的下一个排列，依次查找下去，一直到没有新的排列大于当前排列。

非递归实现算法

这里用一个int数组作为例子辅助说明。
[4, 6, 7, 2, 3, 1, 9]

  1. 对数组进行升序排序。 得到全排列中字典序最小的一个排列：[1, 2, 3, 4 ,6, 7, 9]
  2. 从后往前遍历，找到从最后一个元素往前最大的升序子串。假设该子串为 [k, n - 1]，那么也可以理解为k到n-1是递减的。
    • 如果k == 0，就例子而言，是这样的：[9, 7, 6, 4, 3, 2, 1]。那么其实我们已经找到字典序最大的一个排列，可以结束查找了。
    • 如果k > 0，比方说[1, 2, 3, 4, 9, 7, 6]，k = 5（值是9）。显然还有字典序更大的排列，转3
  3. 将[k, n - 1]区间中大于arr[k - 1]的数中最小的一个与 k - 1 位置的数对换，比方说[1, 2, 3, 4, 9, 7, 6] 变成了 [1, 2, 3, 6, 9, 7, 4]，这里6是区间中满足条件的数。再将区间[k, n -1]做升序排列，变成[1, 2, 3, 6, 4, 7, 9]。
    这里[1, 2, 3, 4, 9, 7, 6] 的下一个排列就是[1, 2, 3, 6, 4, 7, 9]。
  4. 重复2，3直到k == 0。

对算法的简单推理和证明

由于我们是从字典序最小的排列开始，一直到字典序最大的排列结束。那么我们只要证明：上面这个算法，它对一个排列，每次总是能得到字典序只比当前排列大的一个新的排列。就可以证明它的完备性了。
依然用[1, 2, 3, 4, 9, 7, 6] 辅助讲解。
对于这样的一个区间，我们把它划分成3个大区间。
A = [1, 2, 3]， arr[0]~arr[k - 2]
B = [4]， arr[k - 1]
C = [9, 7, 6]， arr[k]~arr[n -1]
C 代表从最后一个元素往前数最大的升序子串[k, n - 1]，B 是区间[k, n - 1]左边那个数–>arr[k - 1]， A 是 [0, k - 2]。A，B，C串起来是完整的一个排列。

再令到 D = B + C = [4, 9, 7, 6]，区间[k - 1, n - 1]。注意A和D串起来跟A，B, C串起来是同一个排列。

那么我们通过算法中的步骤2，找到D这个区间。
现在我们先来证明为什么只需要调整D区间，不需要调整A区间就能获得一个比原排列大的排列。
D区间中，第一个数是arr[k - 1]，我们总能在C区间中找到至少一个数arr[k+i]，比arr[k - 1]要大。那么把arr[k+i]与arr[k - 1]对调的话，就能在D区间上得到一个更大的排列。
为什么不能调整到A区间的元素呢？因为我们希望得到更大的字典序，所以只能对A调整使得A这一部分的字典序大于它原来的排列。但这种方式得到的排列，字典序必然大于只调整D区间的元素，这里读者自己简单推理下就明白了。
就例子而言：我们希望得到的排列是这样的 ：[1, 2, 3, ?, ?, ?, ? ] ，？号备选的数是：4, 6, 7, 9

然后来证明为何将C区间中的比arr[k - 1]大的数中的最小的一个与arr[k - 1]对调。
下面请时刻注意arr[k - 1]是D区间的开头，并且通常说到“排列”二字，是A区间不变，对D区间进行调整的排列。
D区间的元素可以分为3种类型，顺便说明下哪种类型能放到arr[k - 1]这个位置

  1. 小于arr[k - 1]的元素，这部分元素中的任一个调整到D区间的开头，得到的排列（D区间）都是比arr[k - 1]开头的排列要小的。不用考虑了。
  2. 等于arr[k - 1]的元素，注意我们是怎么找到C区间的，就可以知道D区间当前的排列其实是以arr[k - 1]开头的排列中最大的一个，不存在A不变，D区间以arr[k - 1]开头的更大的排列。
  3. 大于arr[k - 1]的元素，如果是希望找到最接近原排列的下一个排列，当然是找这其中最小的一个元素放到arr[k - 1]上啦。就例子来说，这个数是[6]，
    就例子而言：我们希望得到的排列是这样的：[1, 2, 3, 6, ?, ?, ?]，？号备选的数是：4, 7 , 9

现在我们已经把范围缩小到一定程度了。（其实你往前回顾可以看到我一直在缩小可能的区间，使得候选的排列越来越少，并且他们总是最接近原排列的）。
很显然只要把备选的部分[4, 7, 9]作升序排列并到尾部，就可以得到以[1, 2, 3, 6]开头的最小的排列了。
最后结果就是[1, 2, 3, 6, 4, 7, 9]。是字典序大于[1, 2, 3, 4, 9, 7, 6]的排列中最小的一个。

证毕。

上代码

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
52
53
54
55
56
57
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print_arr(vector<int>& arr, int n) {
	int i;
	for (i = 0; i < n; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}
int main() {
	int n;
	int i, k;
	int tem;
	vector<int> arr;
	while (cin >> n) {
		arr.resize(n);
		for (i = 0; i < n; i++)
			cin >> arr[i];
		sort(arr.begin(), arr.end());
		print_arr(arr, n);
		while (true) {
			for (k = n - 2; k >= 0; k--) {
				if (arr[k] < arr[k + 1]) {
					break;
				}
			}
			if (k < 0) {
				break;
			}
			// k > 0
			k += 1;  //   左开右闭区间 --> (k, n - 1]递减，改为左闭右闭区间 -->[k, n - 1]递减
			// 找到[k, n - 1]区间中大于 arr[k - 1]的数中，最小的一个
			for (i = n - 1; i >= k; i--) {
				if (arr[i] > arr[k - 1]) {
					break;
				}
			}
			swap(arr[k - 1], arr[i]);		// 交换
			// 逆序 [k, n - 1]，使得它递增
			for (i = k; i <= (k + (n - 1 - k) / 2); i++) {
				swap(arr[i], arr[n - 1 + k - i]);
			};
			print_arr(arr, n);
		}
	}
	return 0;
}

对比和分析

注意到非递归求全排列，是不会出现重复的排列的。

非递归实现全排列：
空间复杂度：O(n!)
时间复杂度：O(？) < O(n!n) 说实话这种情况我不会求，先给个范围，做个记号，后面回来修改。
为什么小于 O(n!n)呢？找到最长递减序列，最坏的情况也不过是最后一个数到第一个 –> O(n)，逆序也是O(n)。何况并不总是这样，因此不会超过O(n!n)。

递归实现全排列：
空间复杂度：O(n!)
时间复杂度：O(n!nlogn) 去重的情况

非递归没有函数栈，这个优势是很巨大的，同时理论时间复杂度更小。是一种更好的求全排列的方法。

终。