排列问题汇总
一、课上练习
编程练习
- 全排列生成：L3531
二、知识总结
✨ 普通排列问题
从 n 个不同元素中取出 m 个元素进行排列，排列数为 A(n, m) = n! / (n-m)!。这是最基础的排列计算。
✨ 限制选项排列问题
某些元素在某些位置上有限制（如某人不能排在某个位置），通常采用先安排受限元素，再安排其余元素的策略。也可以使用总排列数减去不合要求的排列数（间接法）来求解。
✨ 元素必须相邻排列问题
若干个指定元素必须相邻排列，采用捆绑法：将必须相邻的元素看作一个整体（捆绑在一起），先对整体进行排列，再对整体内部的元素进行排列，最后将两个结果相乘。
✨ 元素必须不相邻排列问题
若干个指定元素互不相邻，采用插空法：先排列其他元素，再将指定元素插入其他元素形成的空隙中（包括两端），从而保证指定元素互不相邻。
✨ 元素定序排列问题
若干个元素之间有固定的相对顺序要求（如 A 必须在 B 前面），则先计算所有元素的全排列，再除以这些定序元素的全排列数。例如 n 个元素中有 k 个元素定序，排列数为 n! / k!。
✨ 环排问题
n 个不同元素排成一个圆环，由于环形排列没有固定的起点，环排数为 (n-1)!。可以理解为：先固定一个元素的位置，其余 n-1 个元素做全排列。
✨ 多排问题
多重排列（有重复元素的排列）：n 个元素中有若干组相同元素，各组分别有 n1, n2, ..., n_k 个，则排列数为：
n! / (n1! × n2! × ... × n_k!)
✨ 错排问题
错排（又称全错位排列）是指 n 个元素排列后，每个元素都不在自己原来的位置上。
错排数公式：
D(n) = (n-1) × (D(n-1) + D(n-2))
其中 D(1) = 0，D(2) = 1。
也可以用容斥原理表示：D(n) = n! × (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n / n!)
✨ 执行示例
以具体例题追踪各类排列问题的解法：
捆绑法示例： 5 人 {A, B, C, D, E} 排成一排，要求 A 和 B 相邻。
步骤1: 将 A、B 捆绑成一个整体 [AB]
步骤2: [AB]、C、D、E 共 4 个元素的全排列 = 4! = 24
步骤3: 整体内部 A、B 可以互换 = 2! = 2
步骤4: 总排列数 = 24 × 2 = 48插空法示例： 5 人 {A, B, C, D, E} 排成一排，要求 A 和 B 不相邻。
步骤1: 先排列 C、D、E = 3! = 6 种
步骤2: C、D、E 形成 4 个空隙：_C_D_E_
步骤3: 将 A、B 插入 4 个空隙中的 2 个 = A(4,2) = 4×3 = 12
步骤4: 总排列数 = 6 × 12 = 72验证：总排列 5!=120，A、B 相邻的 48 种，不相邻 = 120-48 = 72。
定序排列示例： 5 人 {A, B, C, D, E} 排成一排，要求 A 在 B 前面，B 在 C 前面。
A、B、C 三人有固定顺序，定序元素 k = 3
排列数 = 5! / 3! = 120 / 6 = 20环排示例： 5 人围坐在圆桌旁，有多少种不同的坐法？
环排数 = (5-1)! = 4! = 24 种
理解：固定 A 的位置，其余 4 人全排列 = 4! = 24多重排列示例： 用字母 {A, A, B, B, B, C} 排成一排，有多少种不同的排法？
共 6 个元素，A 出现 2 次，B 出现 3 次，C 出现 1 次
排列数 = 6! / (2! × 3! × 1!) = 720 / (2 × 6 × 1) = 60 种错排示例： 3 封信放入 3 个信封，全部放错的方案数。
1D(1) = 0，D(2) = 1
2D(3) = (3-1) × (D(2) + D(1)) = 2 × (1 + 0) = 2
3
4验证：信 {1,2,3}，信封 {1,2,3}
5全排列：123, 132, 213, 231, 312, 321
6全错排：231, 312 → 确实是 2 种✨ 解题步骤详解
排列问题的解题策略选择：
- 看到"相邻" → 用捆绑法：把相邻元素捆绑成一个整体
- 看到"不相邻" → 用插空法：先排其他元素，再在空隙中插入
- 看到"某人不在某位" → 用间接法：总数减去不满足条件的
- 看到"固定顺序" → 用定序法：全排列除以定序元素的排列数
- 看到"围成一圈" → 用环排公式：(n-1)!
- 看到"有重复元素" → 用多重排列公式：n! / (n1! × n2! × ...)
- 看到"全部放错" → 用错排公式：D(n) = (n-1)(D(n-1) + D(n-2))
✨ 常见错误
- 捆绑法忘记内部排列：将元素捆绑后，还要乘以内部元素的排列数
- 插空法空隙数计算错误：n 个元素产生 n+1 个空隙（包括两端），不是 n-1 个
- 环排多算了：环排没有固定起点，直接用 n! 会多算 n 倍，应该用 (n-1)!
- 多重排列漏除：有相同元素时，忘记除以各组相同元素的阶乘
- 定序问题除错对象：应除以定序元素之间的排列数（k!），而不是其位置的排列数
- 环排与项链问题混淆：环排考虑方向（顺/逆时针不同），项链问题不考虑方向（还需再除以 2）
✨ C++ 代码实现
递归生成全排列
1#include <iostream>
2using namespace std;
3
4int n;
5int a[15]; // 存储当前排列
6bool used[15]; // 标记元素是否已使用
7
8void dfs(int step) {
9 if (step > n) {
10 for (int i = 1; i <= n; i++) {
11 cout << a[i] << (i == n ? '\n' : ' ');
12 }
13 return;
14 }
15 for (int i = 1; i <= n; i++) {
16 if (!used[i]) {
17 a[step] = i;
18 used[i] = true;
19 dfs(step + 1);
20 used[i] = false; // 回溯
21 }
22 }
23}
24
25int main() {
26 cin >> n;
27 dfs(1);
28 return 0;
29}输入 3，输出：
11 2 3
21 3 2
32 1 3
42 3 1
53 1 2
63 2 1STL next_permutation
C++ 标准库提供了 next_permutation 函数，可以直接生成下一个字典序排列：
1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5int main() {
6 int n;
7 cin >> n;
8 int a[15];
9 for (int i = 0; i < n; i++) a[i] = i + 1;
10
11 do {
12 for (int i = 0; i < n; i++) {
13 cout << a[i] << (i == n - 1 ? '\n' : ' ');
14 }
15 } while (next_permutation(a, a + n));
16
17 return 0;
18}错排数计算
1#include <iostream>
2using namespace std;
3
4int main() {
5 int n;
6 cin >> n;
7
8 long long d[25];
9 d[1] = 0;
10 d[2] = 1;
11 for (int i = 3; i <= n; i++) {
12 d[i] = (i - 1) * (d[i-1] + d[i-2]);
13 }
14 cout << "D(" << n << ") = " << d[n] << endl;
15
16 return 0;
17}| n | D(n) | 错排比例 D(n)/n! |
|---|---|---|
| 1 | 0 | 0% |
| 2 | 1 | 50% |
| 3 | 2 | 33.3% |
| 4 | 9 | 37.5% |
| 5 | 44 | 36.7% |
| 10 | 1334961 | 36.8% |
随着 n 增大，错排比例趋近于 1/e ≈ 36.8%，这是一个有趣的数学事实。
有重复元素的排列
1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5int main() {
6 int n;
7 cin >> n;
8 int a[15];
9 for (int i = 0; i < n; i++) cin >> a[i];
10
11 // 先排序，确保从最小字典序开始
12 sort(a, a + n);
13
14 int count = 0;
15 do {
16 for (int i = 0; i < n; i++) {
17 cout << a[i] << (i == n - 1 ? '\n' : ' ');
18 }
19 count++;
20 } while (next_permutation(a, a + n));
21
22 cout << "共 " << count << " 种排列" << endl;
23 return 0;
24}输入 4 和 1 1 2 2 时，输出 6 种排列（而不是 4!=24 种），因为 4!/(2!×2!)=6。
✨ 综合例题
例题： 6 人站成一排拍照，其中甲不站第一位，乙不站最后一位，共有多少种排法？
分析： 直接计算不方便，用容斥原理。
1设 A = 甲站第一位的排列，B = 乙站最后一位的排列
2|A| = 5! = 120（甲固定第一位，其余 5 人全排列）
3|B| = 5! = 120（乙固定最后，其余 5 人全排列）
4|A∩B| = 4! = 24（甲第一、乙最后，其余 4 人全排列）
5
6不满足条件的 = |A| + |B| - |A∩B| = 120 + 120 - 24 = 216
7满足条件的 = 6! - 216 = 720 - 216 = 504 种