Permutation(排列与置换)
Ishy
·
·
算法·理论
Permutation
Permutation(排列)
Definition (Permutation)
排列 (全排列)：将 n 个不同的元素排成一列，称为这 n 个元素的排列。
大小为 n 的排列又叫做 n 元排列。
Definition (Inversion)
逆序对：对于 n 个元素，如果它们构成了一个全序 (即任意两个元素之间都可以比较)，对于它们的一个排列，如果两个元素在排列中的顺序与全序中的顺序不同，则称它们是一个逆序对。
逆序数：一个排列 σ 中所有逆序的总数叫做这个排列的逆序数，记作 N(σ)。
Definition (Parity of A Permutation)
奇排列 (Odd permutation)：若一个排列的逆序数为奇数，则称它为奇排列。
偶排列 (Even permutation)：若一个排列的逆序数为偶数，则称它为偶排列。
排列的符号：一个排列 σ 的符号 (Sign) 定义为 \operatorname{sgn} (σ) = (-1)^{N(σ)}，即，奇排列的符号为 -1，偶排列的符号为 1。
Permutation (置换)
Permutation(置换)
一个置换可以看成一个一一映射 (双射) g : [n] → [n]，满足 g (i) = p_i。
(注： [n] 表示集合 \{1, 2, · · · , n\})
为了强调置换是一种变换/映射，我们通常使用 2 × n 的矩阵来表示一个置换：
g=\begin{pmatrix}
1 & 2 & \cdots & n \\
p_1 & p_2 & \cdots & p_n
\end{pmatrix}
Inverse of A Permutation
Definition (Inverse of A Permutation)
对一个置换 g=\begin{pmatrix}
1 & 2 & \cdots & n \\
p_1 & p_2 & \cdots & p_n
\end{pmatrix}，定义它的逆为 g^{-1}=\begin{pmatrix}
p_1 & p_2 & \cdots & p_n \\
1 & 2 & \cdots & n
\end{pmatrix}。
即 g^{-1}(g(i))=i。
Theorem 1
一个置换和它的逆具有相同的逆序数和符号。
Special Permutations
恒等置换
#### 对换
仅有一个二元组满足 $g(i)=j,g(j)=i$，对于其它的 $1\le k \le n,k\ne i,k\ne j$ 满足 $g(k)=k$。
则称 $g$ 是一个对换，记作 $s_{i,j}$。
- 将一个置换 $g$ 与对换进行合成，相当于交换置换(排列) $g$ 中的两个元素。（见下文合成的定义）
### Composition
> **Definition (Composition)**
>
> 设 $f=\begin{pmatrix}
1 & 2 & \cdots & n \\
i_1 & i_2 & \cdots & i_n
\end{pmatrix}$，$g=\begin{pmatrix}
1 & 2 & \cdots & n \\
j_1 & j_2 & \cdots & j_n
\end{pmatrix}$。
>
> $f$ 与 $g$ 的合成记作 $f\circ g$，简写作 $fg$。
>
> 有 $(g\circ f)(k)=g(f(k))=j_{i_k}$。
- $g◦g^{-1}=g^{-1}◦g=e$。
- $(f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h$。
- $g^k=g\circ g\circ g\circ \cdots \circ g$（$k$ 个 $g$）。
- 合成不满足交换律。
- 消去律：若 $f\circ g=h\circ g$，则 $f=h$。
考虑两边乘上 $g^{-1}$。
### Permutation And Sign
> **Theorem 2 **
>
> 对于大小相同的置换 $f,g$，有 $\operatorname{sgn}(f\circ g)=\operatorname{sgn}(f) \cdot \operatorname{sgn}(g)$。
- **所有的对换均为奇置换。**
> **Corollary 1**
>
> 交换置换中的两个元素，改变置换的奇偶性。
> **Theorem 3**
>
> 交换置换 $g$ 中相邻的两个元素 $p_i, p_j$，如果 $p_i < p_j$，则交换后置换的逆序数为 $N (g) + 1$，否则为 $N (g) - 1$。
## Cycle(循环)
### Cycle And Graph
> **Definition (Cycle)**
>
> 对 $L$ 个元素的一个排列 $a_1, a_2, · · · , a_L$，如果置换 $g$ 满足 $g (a_1) = a_2, g (a_2) = a_3, · · · , g (a_{L-1}) = a_L, g (a_L) = a_1$，则称置换 $g$ 为一个循环 (或轮换)，简记为 $(a_1 \,\,\, a_2 \,\,\, a_3 · · · a_{L-1} \,\,\, a_L)$， $L$ 称为该循环的长度。
> **Definition (Cycle Notation)**
>
> 对 $n$ 元置换 $g$，称下式为 $g$ 的循环表示：$g = (a_{11}a_{12} · · · a_{1L_1}) (a_{21}a_{22} · · · a_{2L_2}) · · · a_{y1}a_{y2} · · · a_{yL_y}$。
>
> 其中 $g (a_{ij}) = a_{i,j+1}, g (a_{iL_i}) = a_{i1}, L_1 + L_2 + · · · + L_y = n(1 ≤ j < L_i)$，且所有 $a_{ij}$ 互不相同。
>
> $y$ 为置换 $g$ 的循环表示中的循环数，记作 $\# (g)$，在上下文已知的情况下可记为 $\#$。
- 如果有一个循环的长度为 $1$，则可以省略不写。
- 循环合成置换。
- 与图论的联系。
一个循环可以表示成一个有向图，且该图恰为一个环。
每个循环相互独立。
### 对换对循环的影响
同一个循环里的对换：
不同循环的对换：
> **Theorem 4**
>
> 任意交换置换 $g$ 中的两个元素，则交换后置换的循环数与原置换 $g$ 的循环数 $\# (g)$ 的差为 $±1$。
>
> 即 $|\# (g ◦ s_{i,j}) - \# (g)| = 1$。
见上图。
> **Corollary 2**
>
> 一个 $n$ 元置换 $g$ 是偶置换的充分必要条件是，它的循环数 $\# (g) ≡ n (\operatorname{mod}\, 2)$。
排序后的最终状态是形成 $n$ 个长度为 $1$ 的循环。
由定理 $4$，每次对换能改变循环个数，那么我每次选同一个循环中的两个元素交换，都会使循环数加一。
即使序列从小到大有序的最小交换次数为 $n-\#(g)$。
结合 Corollary 1，每次对换改变置换的奇偶性。
由最终状态是一个偶置换（逆序数为 $0$）回推，可知 $\#(g)-n$ 的奇偶性就是置换 $g$ 的奇偶性。
### 置换快速幂
假设一个循环的长度为 $L$，则在模 $L$ 意义下，$g^{k}(a_i)=a_{i+k}$。
可以避免使用传统的 $O(n\log{n})$ 快速幂算法，转用 **平移** 的方法 $O(n)$ 解决问题。
对于一个置换，将其中的所有循环都这样处理即可。
## Cycle Index(循环指标)
### Cycle Index
> **Definition (Cycle Index)**
>
> 对 $n$ 元置换 $g$，设 $g$ 的循环表示为 $g = (a_{11}a_{12} · · · a_{1L_1}) (a_{21}a_{22} · · · a_{2L_2}) · · · (a_{y1}a_{y2} · · · a_{yL_y})$。
>
> 设这些循环中有 $\#_i$ 个循环大小为 $i$，则定义 $g$ 的循环指标为 $ t_1^{\#_1} t_2^{\#_2}· · · t_n^{\#_n}$，
>
> 其中 $t_i$ 为形式变元，就像生成函数中的 $x$ 一样。
- $\#_1+\#_2+\cdots +\#_n=\#(g)$。
- $1\#_1+2\#_2+\cdots+ n\#_n =n$。
$g$ 的所有循环的长度 $L_1, L_2, · · · , L_y$ 构成了整数 $n$ 的一种拆分 (partition)。
$n$ 元置换的每一种循环指标，都唯一对应着整数 $n$ 的一种拆分方案，相反，整数 $n$ 的每一种拆分方案，都唯一确定着 $n$ 元置换的某一种循环指标。
拆分的方案记作拆分数 $p(n)$，例如 $p(5)=7$。
（5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1）
### 固定循环指标的置换计数
> **Problem**
>
> 给定一个循环指标 $ t_1^{\#_1} t_2^{\#_2}· · · t_n^{\#_n}$，求有多少个 $n$ 元置换以它为循环指标。
先把每个循环里的数确定下来，由可重组合公式，方案数为 $\frac{n!}{(1!)^{\#_1}(2!)^{\#_2}\dots(n!)^{\#_n}}$。
相当于在总的方案中除掉在一个循环中那些相同的数自行排列的重复方案。
相同长度的循环可以形成排列，还要除掉这些重复的方案，新的方案数为 $\frac{n!}{(1!)^{\#_1}(2!)^{\#_2}\dots(n!)^{\#_n}(\#_1)!(\#_2)!\dots(\#_n)!}$。
每个循环内可以形成圆排列，要考虑这些不重复的方案，因此方案数乘上 $\prod\limits_{i=1}^{n}((i-1)!)^{\#_i}$，答案为：
$$
\frac{n!}{1^{\#_1}2^{\#_2}\dots n^{\#_n}(\#_1)!(\#_2)!\dots(\#_n)!}
$$
## Order(阶)
> **Definition (Order)**
>
> 对于置换 $g$，使得 $g^k = e$ 成立的最小的正整数 $k$ 称为 $g$ 的阶，记作 $|g|$。
注意阶和元的区分。
- 置换 $g$ 的阶为 $1$ 当且仅当 $g$ 为恒等置换 $e$。
- 置换 $g$ 的阶为 $2$ 当且仅当 $g$ 为非恒等置换的对合置换。
- 若 $n$ 元置换 $g$ 是循环，则 $|g| = n$ (逆命题不一定成立，如置换 (1 2) (3 4 5) (6) 的阶也是 6)。
> **Theorem 5**
>
> 一个置换的阶等于构成它的所有循环长度的最小公倍数。
>
> 即 $|g|=\operatorname{lcm}(L_1,L_2,\dots,L_y)$。
## 置换的循环数分布
> **Theorem 6**
>
> 含有 $k$ 个循环的 $n$ 元置换的数量为 ${{n}\brack{k}}$，其中 ${{n}\brack{k}}$ 为第一类 Stirling 数，定义如下：
> $$
x^{\overline{n}}=\sum\limits_{i=0}^{n}
\begin{bmatrix}
n \\
k \\
\end{bmatrix}
x^i
$$
> **Corollary 3**
>
> 对 $n ≥ 2$， $n$ 元奇置换和偶置换的个数相等，都等于 $\frac{n!}{2}$。
## 置换的逆序数分布
> **Problem**
>
> 研究 $k$ 个逆序对的 $n$ 元置换数。
设逆序数为 $j$ 的 $i$ 元置换数为 $f_{i,j}$。
令生成函数 $F_i(x)=\sum\limits_{j}f_{i,j}x^j$。
对于 $i-1$ 元置换插入 $i$，由于 $i$ 是最大的，因此考虑不同的插入位置，必然可以产生 $0,1,2,\cdots,i-1$ 个逆序对的贡献。即：
$$
F_i(x)=F_{i-1}(x)(1+x+x^2+x^3+\cdots+x^{i-1})
$$
递推得：
$$
F_n(x)=(1+x)(1+x^2)\cdots(1+x^{n-1})
$$
则 $[x^k]F_n(x)$ 即为答案。
具体实现时，考虑该式可化成另一种形式：
$$
F_n(x)=\frac{(1-x)(1-x^2)\cdots (1-x^n)}{(1-x)^n}
$$
~~yhx大佬说可以多项式 ln/exp，但我不会。~~
分母可以这样化：$\sum\limits_{i}{{n+i-1}\choose{n-1}}x^i$。
分子的意义是，从 $1$ 到 $n$ 选 $i$ 个数（$i\in[0,n]$），总和为 $j$，对该项系数(选取方案)贡献为 $(−1)^i$。
这玩意儿可以用背包做，思想就是维护一个升序的选取方案，满足前后两项差值为正。
由于选择的数互不相同，因此能选的数很少，小于 $\sqrt{2k}$，保证了复杂度正确。
具体做法是：
令 $f_{i,j}$ 表示选取 $i$ 个数，和为 $j$ 的方案数。
看网上有人说这种做法叫柱状图 dp，我觉得还挺形象。考虑 $3$ 种情况：
- 将 $i$ 个数集体加 $1$，$f_{i,j}+=f_{i,j-i}$。
- 将 $i-1$ 个数集体加 $1$ 后在最前面插入 $1$，共 $i$ 个数，$f_{i,j}+=f_{i-1,j-i}$。
- 由于每次操作前都让所有数加 $1$，所以 $j>n$ 会出现最后一项为 $n+1$ 的情况，
此时令 $f_{i,j}-=f_{i-1,j-(n+1)}$，可看作是减掉在末尾加上 $n+1$ 的转移方案。
最后把分子分母的展开形式卷起来即可。
可做到 $n,k\le 10^5$，原题见 LOJ6077。
~~没取模 加爆了~~