constrained · 插空法 / 捆绑法

带约束的排列：插空法与捆绑法

现实里的排列常带一句附加条件，最常见的两类是「某些元素两两不相邻」与「某些元素必须相邻」。它们各有一个对偶的标准技巧——插空法与捆绑法——而两者都不是新公式，只是乘法原理与排列数 P(n, k) 的组合运用：把「无约束的部分」先排好，再用一步受控的选位安置「受约束的部分」。

1 · 插空法：不相邻，就先排骨架、再往空隙里插

non-adjacent · k! × P(k+1, m)

要让 m 个元素两两不相邻，正面逐个排布很难保证这个条件。换个角度：先把其余 k 个「可以相邻」的元素排成一列（骨架），这一步有 k! 种。骨架排好后，元素之间与两端一共形成 k+1 个空隙；只要让每个受约束元素各占一个不同的空隙，它们就被骨架天然隔开、必不相邻。从 k+1 个空隙里有序地放入 m 个，正是 P(k+1, m)。拖动下方滑块，看空隙数如何随骨架长度变化。

2 · 把插法逐个列出来

enumerate · 固定骨架的 P(k+1, m) 种插法

为看清「插空」这一步，下面把骨架固定为 $A, B, C, \dots$ （不再排它的 k! 种顺序），只枚举把 X, Y, Z 插入空隙的全部 P(k+1, m) 种结果。留意每一行里高亮的插入元素之间，至少隔着一个骨架元素——这正是不相邻的由来。完整方案数还要把骨架自身的 k! 种顺序乘回来。

3 · 捆绑法：必须相邻，就先捆成一个整体

adjacent · (k+1)! × m!

对偶的问题是让 m 个元素必须相邻。既然它们必须连在一起，就把这 m 个捆成一个整体，当作单独一个元素，与其余 k 个自由元素一起排——共 k+1 个「单元」，有 (k+1)! 种。捆内部这 m 个元素自己还能换序，再乘 m!。于是方案数是 $(k+1)! \times m!$ 。拖动滑块，看「捆」如何作为一个整体参与排列。

插空与捆绑是一对互补的思路：不相邻用插空（把受约束元素拆开塞进不同空隙），相邻用捆绑（把受约束元素合并成一个整体）。两者都把「带约束的排列」化归为一次普通全排列加一步 P 或 m! 的选序，本质仍是排列 P(n, k)。若要按字典序真正生成这些排列，见算法系列排列生成。

4 · 相关链接

Permutation — Wikipedia · en.wikipedia.org——排列与 P(n, k)，带约束排列是其常见变体。
Inclusion–exclusion — Wikipedia · en.wikipedia.org——当约束更复杂（多组不相邻）时，插空之外还需容斥。