生成字典序的全排列算法

代码测试模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <numeric>
using namespace std;

constexpr int n = 4;
int a[n];
inline void init() {
    iota(a, a + n, 1);
}
inline void printA() {
    for (int x : a)
        cout << x;
    cout << endl;
}

1. 交换元素法

《剑指Offer》第一版的面试题28：字符串的排列，书上给出的递归算法实现如下：

1
2
3
4
5
6
7
8
9
void Permutation(int k) {
    if (k == n)
        printX();
    for (int i = k; i < n; i++) {
        swap(a[i], a[k]);
        Permutation(k + 1);
        swap(a[i], a[k]);
    }
}

这种做法的问题是，得出的结果无法保持字典序，比如n=4时，1432在1423前面，原因是4和2交换后，后面的3和2就失去了有序性。
那么对后面进行排序呢？也不行，如果排序之后，2的位置变了，之后调用的swap(a[1], a[3])交换的便是4和3而非4和2。

2. DFS

其实字典序排序的就是找到N叉树的所有根节点到叶子节点的路径，以123为例

1
2
3
4
5
6
7
       [ ]
    /   |   \
  1     2     3
 / \   / \   / \
2   3 1   3 1   2
|   | |   | |   |
3   2 3   2 2   1

构造出这棵树，然后DFS即可。问题是如何构造？实际上是N叉树剪枝。剪枝通过为每个节点设置标志来判断，无需用哈希表，每个节点对应数组的一个下标。实现如下：
先添加全局变量以及修改init()函数

1
2
3
4
5
6
7
8
9
#include <algorithm>
// ...
bool visited[n];
int a0[n];  // 保存a[n]的原始数据
inline void init() {
    iota(a0, a0 + n, 1);
    copy(a0, a0 + n, a);
    fill(visited, visited + n, false);
}

然后实现递归函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int k) {
    if (k >= n) {
        printA();
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {  // 剪枝
            visited[i] = true;
            a[k] = a0[i];
            dfs(k + 1);
            visited[i] = false;
        }
    }
}

3. STL算法

STL提供了现成的函数来提供下一个字典序(默认)排列

1
2
3
4
sort(a, a + n);
do {
    printA();
} while (next_permutation(a, a + n));

因此上述代码就足以实现算法了，这里主要研究下next_permutation()的实现。
next_permutation()生成的是下一个较大的序列，比如对123生成的就是132而非213、231，因为不存在大小范围在123和132之间的排列。
设当前序列为a[n]，且存在i使得a[i]>a[i+1]>…>a[n-1]。此时无法通过交换a[i]到a[n-1]之间的两个元素使其字典序更大。
因此必须将a[i-1]和a[i]..a[n-1]之间一个比a[i-1]大的数交换，比如对153642，后缀642单调递减，因此得交换3和6、4、2的一个数。而交换2会使字典序减小，因此交换4，得到154632，由于6>4>3>2，相当于3插入2和4之间，因此后缀632是单调递减，需要将其逆置来获得最小字典序。
具体证明这里不详述，可参考全排列生成算法: next_permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool NextPermutation() {
    if (n <= 1)
        return false;
    // 找出右边最大递减序列a[i..n-1]
    int i = n - 1;
    while (i > 0 && a[i - 1] >= a[i])
        i--;
    if (i == 0) {  // 整个a[n]为降序
        std::reverse(a, a + n);  // 恢复成初始的升序状态
        return false;  // 已经是最大字典序
    }

    int j = std::lower_bound(a + i, a + n, a[i - 1], std::greater<int>()) - a - 1;
    swap(a[i - 1], a[j]);
    std::reverse(a + i, a + n);
    return true;
}

这种做法还有个优点就是避免了重复输出。
比如对序列112，用DFS做会生成两个112。而用这种方法做：

  1. a[1]和a[2]交换，得到121；
  2. a[0]和a[1]交换，得到211，结束。

因为每次交换的是a[i-1]和大于a[i-1]的a[j]，因此不会像交换法或DFS一样将a[i-1]和相等的a[j]交换。
这里使用lower_bound()在降序序列中进行二分查找，找到用来和a[i-1]交换的a[j]。而STL直接是从后往前查找，原因是next_permutation()是基于双向迭代器的，无法应用于二分查找。虽然理论上我这种做法更快，但实际上生成全排列的时间复杂度是O(n!)，n不可能很大，充其量上两位数，相比起全排列本身的复杂度，O(n)到O(logn)的效率提升实际上无关痛痒。