全排列算法（Full Permutation）

定义#

给定无重复元素序列 $\{a_n\}$ ，即满足：

1 \leq i,j \leq n \land i \neq j \Rightarrow a_i \neq a_j,

从中任取 $m$ （ $m \leq n$ ）个元素并按顺序排成一列，得到的所有结果称为排列（Permutation / Arrangement）。当 $m < n$ 时，排列数为

A_n^m = \frac{n!}{(n-m)!}

当 $m = n$ 时称为全排列（Full Permutation），排列数为

A_n^n = n!

全排列的实现可分为递归与非递归两类。下文示例默认序列元素为 $1, \cdots, n$ 的整数；换成字符等其它可比较类型亦可。

递归实现#

1. 交换法#

由 $A_n^n = n \cdot A_{n-1}^{n-1}$ ：将 $\{a_n\}$ 中每个元素依次固定到某一位置（通常是当前位置 $k$ ），再对剩余 $n-1$ 个元素求全排列，直到只剩一个元素。

以 $\{1,2,3\}$ 为例，先固定首位：

交换	结果
$a_0 \leftrightarrow a_0$	$1,2,3$
$a_0 \leftrightarrow a_1$	$2,1,3$
$a_0 \leftrightarrow a_2$	$3,2,1$

再对每个结果的后两位继续交换，最终得到全部 $3! = 6$ 种排列。

步骤：

固定位索引 $k = 0$ ；
对所有 $i \in [k, n)$ ，交换 $a_k$ 与 $a_i$ ，再递归处理 $k+1$ ；
递归返回后交换回来（回溯）；
当 $k = n-1$ 时输出一种排列。

1
#include <iostream>
2
using namespace std;
3

4
int n;
5

6
void swap(int *a, int *b) {
7
    *a ^= *b;
8
    *b ^= *a;
9
    *a ^= *b;
10
}
11

12
void permutation(int array[], int k) {
13
    if (k == n - 1) {
14
        for (int i = 0; i < n; i++) {
15
            cout << array[i] << ' ';
16
        }
17
        cout << endl;
18
    } else {
19
        for (int i = k; i < n; i++) {
20
            swap(&array[i], &array[k]);
21
            permutation(array, k + 1);
22
            swap(&array[i], &array[k]);
23
        }
24
    }
25
}
26

27
int main() {
28
    cin >> n;
29
    int a[n];
30
    for (int i = 0; i < n; ++i) {
31
        a[i] = i + 1;
32
    }
33
    permutation(a, 0);
34
    return 0;
35
}

注意即便输入已是字典序，交换法得到的输出顺序一般也不是字典序。

复杂度： 递归会到达 $n!$ 个叶结点；若每次输出花费 $O(n)$ ，生成全部全排列的时间为 $O(n \cdot n!)$ 。递归深度为 $O(n)$ ，除输入数组外额外栈空间为 $O(n)$ 。

2. 递归生成树法#

另一视角： $A_n^n = \prod_{k=1}^{n} C_k^1$ 。维护一个栈：每次从剩余元素中取一个入栈，递归；返回后出栈并把元素放回。对序列 $\{a_3\} =$ {1,2,3}$ 可画出递归生成树，根到叶的每条路径对应一种排列：

用 vector 容器同时表示剩余序列与结果栈，即可实现递归生成树法：

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4

5
vector<int> res;
6
vector<int> a;
7
int n;
8

9
void permutation(int k) {
10
    if (k == 0) {
11
        for (int i = 0; i < n; ++i) {
12
            cout << res[i] << ' ';
13
        }
14
        cout << endl;
15
    } else {
16
        for (int i = 0; i < k; ++i) {
17
            res.push_back(a[i]);
18
            a.erase(a.begin() + i);
19
            permutation(k - 1);
20
            a.insert(a.begin() + i, res.back());
21
            res.pop_back();
22
        }
23
    }
24
}
25

26
int main() {
27
    cin >> n;
28
    for (int i = 0; i < n; ++i) {
29
        a.push_back(i + 1);
30
    }
31
    permutation(n);
32
    return 0;
33
}

vector 的 erase / insert 会使后续元素整体移动，常数较大；可用链表降低移动开销，但实现更繁琐。生成全部排列并输出时，时间仍至少是 $O(n \cdot n!)$ 量级，额外空间 $O(n)$ 。

非递归实现#

3. 穷举法#

穷举法的思路与递归生成树类似：用 $n$ 层嵌套循环依次选位置，并用条件排除重复。但其缺陷也很明显：代码的循环层数绑死 $n$ ，一般只适用于 $n$ 固定的情况。

$n = 5$ 时示意代码如下：

1
#include <iostream>
2
using namespace std;
3

4
int n = 5;
5

6
int main() {
7
    int a[n];
8
    for (int i = 0; i < n; ++i) {
9
        a[i] = i + 1;
10
    }
11
    for (int i1 = 0; i1 < n; ++i1) {
12
        for (int i2 = 0; i2 < n; ++i2) {
13
            if (a[i1] == a[i2]) continue;
14
            for (int i3 = 0; i3 < n; ++i3) {
15
                if (a[i1] == a[i3] || a[i2] == a[i3]) continue;
16
                for (int i4 = 0; i4 < n; ++i4) {
17
                    if (a[i1] == a[i4] || a[i2] == a[i4] || a[i3] == a[i4]) continue;
18
                    for (int i5 = 0; i5 < n; ++i5) {
19
                        if (a[i1] == a[i5] || a[i2] == a[i5] || a[i3] == a[i5] || a[i4] == a[i5]) continue;
20
                        cout << a[i1] << ' ' << a[i2] << ' ' << a[i3] << ' '
21
                             << a[i4] << ' ' << a[i5] << endl;
22
                    }
23
                }
24
            }
25
        }
26
    }
27
    return 0;
28
}

若输入无重复且按字典序给出，输出也会按字典序。嵌套循环的搜索规模约为 $O(n^n)$ 量级，额外空间 $O(n)$ 。

4. 字典序法（`next_permutation` / `prev_permutation`）#

$n!$ 种全排列可排成字典序序列 $\{P_k\}$ ：

$P_1$ ：原序列的字典序最小排列；
$P_{n!}$ ：反字典序（字典序最大）；
$P_k$ 可由 $P_{k-1}$ 通过求下一个排列得到。

例如 $\{A,B,C,D,E,F\}$ ： $P_1 = ABCDEF$ ， $P_2 = ABCDFE$ ，…， $P_{720} = FEDCBA$ 。

C++ <algorithm> 提供 next_permutation / prev_permutation。常见用法：

先 sort 成升序，再循环 next_permutation 直到返回 false；
或先变成降序，再循环 prev_permutation；
也可从任意排列双向扫完所有排列。

1
#include <iostream>
2
#include <algorithm>
3
#include <string>
4
using namespace std;
5

6
void print(const string &s) {
7
    for (char c : s) {
8
        cout << c << ' ';
9
    }
10
    cout << endl;
11
}
12

13
void LFP(string str) { // Lexicographical Full Permutation
14
    sort(str.begin(), str.end());
15
    do {
16
        print(str);
17
    } while (next_permutation(str.begin(), str.end()));
18
}
19

20
void RLFP(string str) { // Reverse Lexicographical Full Permutation
21
    sort(str.begin(), str.end());
22
    reverse(str.begin(), str.end());
23
    do {
24
        print(str);
25
    } while (prev_permutation(str.begin(), str.end()));
26
}
27

28
int main() {
29
    string str;
30
    cin >> str;
31
    LFP(str);
32
    RLFP(str);
33
    return 0;
34
}

next_permutation 步骤（有重复元素时用 $\leq$ / $\geq$ 亦可）：

从右往左找最大下标 $k$ ，使 $a_k < a_{k+1}$ （找不到则已是最后一项）；
从右往左找最大下标 $j > k$ ，使 $a_k < a_j$ ；
交换 $a_k$ 与 $a_j$ ；
将区间 $[k+1, n)$ 反转，得到下一个字典序排列。

prev_permutation 将上述比较方向反过来即可。对应实现如下：

1
#include <iostream>
2
using namespace std;
3

4
void swap(int *a, int *b) {
5
    *a ^= *b;
6
    *b ^= *a;
7
    *a ^= *b;
8
}
9

10
int main() {
11
    int n;
12
    cin >> n;
13
    int a[n];
14
    for (int i = 0; i < n; ++i) {
15
        a[i] = i + 1;
16
    }
17
    while (true) {
18
        for (int i = 0; i < n; i++) {
19
            cout << a[i] << ' ';
20
        }
21
        cout << endl;
22

23
        int k = n - 2;
24
        int j = n - 1;
25
        // prev_permutation：把 >= 改成 <=
26
        for (; k >= 0 && a[k] >= a[k + 1]; --k) {}
27
        if (k == -1) {
28
            break;
29
        }
30
        for (; j > k && a[k] >= a[j]; --j) {}
31
        swap(&a[j], &a[k]);
32
        for (int i = 0; i < (n - 1 - k) / 2; ++i) {
33
            swap(&a[k + 1 + i], &a[n - 1 - i]);
34
        }
35
    }
36
    return 0;
37
}

单次 next_permutation 为 $O(n)$ ，枚举全部为 $O(n \cdot n!)$ ，额外空间 $O(1)$ （原地）。

5. Steinhaus–Johnson–Trotter（SJT）算法#

SJT 又称最小改动排列生成算法，其通过相邻交换依次得到下一个排列：为每个元素维护移动方向；每次找出可合法移动的最大元素，与其方向上的相邻元素交换，并翻转所有更大元素的方向，直到没有元素可移动。其具体实现如下：

1
#include <iostream>
2
using namespace std;
3

4
void swap(int &a, int &b) {
5
    a ^= b;
6
    b ^= a;
7
    a ^= b;
8
}
9

10
void print(int a[], int n) {
11
    for (int i = 0; i < n; ++i) {
12
        cout << a[i] << ' ';
13
    }
14
    cout << endl;
15
}
16

17
int main() {
18
    int n;
19
    cin >> n;
20
    int a[n], d[n];
21
    for (int i = 0; i < n; ++i) {
22
        a[i] = i + 1;
23
        d[i] = -1; // -1 向左，+1 向右
24
    }
25
    bool flag = true;
26
    while (flag) {
27
        flag = false;
28
        print(a, n);
29
        int mx = 0;
30
        int max_index = 0;
31
        for (int i = 0; i < n; ++i) {
32
            if ((d[i] < 0 && i > 0 && a[i] > a[i - 1]) ||
33
                (d[i] > 0 && i < n - 1 && a[i] > a[i + 1])) {
34
                if (a[i] > mx) {
35
                    mx = a[i];
36
                    max_index = i;
37
                    flag = true;
38
                }
39
            }
40
        }
41
        if (!flag) {
42
            break;
43
        }
44
        swap(a[max_index], a[max_index + d[max_index]]);
45
        swap(d[max_index], d[max_index + d[max_index]]);
46
        for (int i = 0; i < n; ++i) {
47
            if (a[i] > mx) {
48
                d[i] = -d[i];
49
            }
50
        }
51
    }
52
    return 0;
53
}

IMPORTANT

初始为字典序时，SJT 的生成顺序通常也不是字典序。时间 $O(n \cdot n!)$ ，空间 $O(n)$ （含方向数组）。

应用：填数问题#

全排列本质是穷举。若必须枚举全部排列，时间至少 $O(n \cdot n!)$ ，只适合规模较小的问题。在解题经验上，时限约 $1000\,\mathrm{ms}$ 、 $O(n!)$ 量级时， $n \leq 11$ 是一般而言可行的规模上限；若剪枝得当有时 $n$ 可到 $12$ 或 $13$ 。

例题： 2016 年第七届蓝桥杯省赛 C 语言 A 组第 3 题——在如下十格填入 $0$ – $9$ （各用一次），要求任意两个连续整数（差的绝对值为 $1$ ）所在格不能相邻（含斜向）。

该问题本质是图上的约束计数，一般用 DFS 来解决。但考虑到本题的规模，也可先求全排列，再通过特殊的判定条件筛选出满足条件的排列。下面用字典序法枚举所有排列并逐个判断是否满足条件。

1
#include <iostream>
2
#define n 10
3
#define abs(a) ((a) > 0 ? (a) : -(a))
4
using namespace std;
5

6
void swap(int *a, int *b) {
7
    *a ^= *b;
8
    *b ^= *a;
9
    *a ^= *b;
10
}
11

12
int main() {
13
    int *a = new int[n];
14
    for (int i = 0; i < n; ++i) {
15
        a[i] = i;
16
    }
17
    int count = 0;
18
    while (true) {
19
        if (abs(a[0] - a[1]) != 1 && abs(a[1] - a[2]) != 1 &&
20
            abs(a[3] - a[4]) != 1 && abs(a[4] - a[5]) != 1 && abs(a[5] - a[6]) != 1 &&
21
            abs(a[7] - a[8]) != 1 && abs(a[8] - a[9]) != 1 &&
22
            abs(a[0] - a[4]) != 1 && abs(a[1] - a[5]) != 1 && abs(a[2] - a[6]) != 1 &&
23
            abs(a[3] - a[7]) != 1 && abs(a[4] - a[8]) != 1 && abs(a[5] - a[9]) != 1 &&
24
            abs(a[0] - a[5]) != 1 && abs(a[1] - a[6]) != 1 &&
25
            abs(a[3] - a[8]) != 1 && abs(a[4] - a[9]) != 1 &&
26
            abs(a[0] - a[3]) != 1 && abs(a[1] - a[4]) != 1 && abs(a[2] - a[5]) != 1 &&
27
            abs(a[4] - a[7]) != 1 && abs(a[5] - a[8]) != 1 && abs(a[6] - a[9]) != 1) {
28
            count++;
29
        }
30
        int k = n - 2, j = n - 1;
31
        for (; k >= 0 && a[k] > a[k + 1]; --k) {}
32
        if (k == -1) {
33
            break;
34
        }
35
        for (; j > k && a[k] > a[j]; --j) {}
36
        swap(&a[j], &a[k]);
37
        for (int i = 0; i < (n - 1 - k) / 2; ++i) {
38
            swap(&a[k + 1 + i], &a[n - 1 - i]);
39
        }
40
    }
41
    cout << count << endl;
42
    delete[] a;
43
    return 0;
44
}

答案为 1580。

音乐

音乐

定义#

递归实现#

1. 交换法#

2. 递归生成树法#

非递归实现#

3. 穷举法#

4. 字典序法（`next_permutation` / `prev_permutation`）#

5. Steinhaus–Johnson–Trotter（SJT）算法#

应用：填数问题#

文章分享

评论区

音乐

音乐

全排列算法（Full Permutation）

定义#

递归实现#

1. 交换法#

2. 递归生成树法#

非递归实现#

3. 穷举法#

4. 字典序法（next_permutation / prev_permutation）#

5. Steinhaus–Johnson–Trotter（SJT）算法#

应用：填数问题#

文章分享

评论区

4. 字典序法（`next_permutation` / `prev_permutation`）#