[复习资料][随想]如何枚举一个排列

[随想]如何枚举一个排列

感觉最近博客里啥也没有写了，赶紧来写个东西让博客看起来没有那么冷清（大雾

有这样一类问题，需要你去枚举大小为 (n) 的全排列，此时可以从下面几种方法去考虑：

1. “直接枚举”。枚举每个位置选的是哪个数，或者枚举每个数放在哪个位置。
2. “插入法枚举”。从左到右考虑每个位置选择的数在前缀的排名，类似在前面排好序的所有数中插入一个数，或者从小到大枚举每个数插在的相对位置。
3. “状压枚举”。从左到右考虑每个位置，状压已经使用过的所有数。
4. “置换枚举/划分数枚举”。将排列看做是一个置换，此时可以通过枚举划分数来枚举每个置换的大小，如果已经知道每个置换的大小分别是 (a_1,a_2,dots,a_k(sum_{i=1}^ka_i=n)) ，大小为 (i) 的置换个数为 (b_i) ，那么置换大小恰好这么多的排列个数是 (frac{n!}{prod_{i=1}^ka_iprod_{i=1}^nb_i!}) 。
5. “笛卡尔树枚举”。枚举笛卡尔树上面每个点的父亲编号，或者枚举笛卡尔树上每个点的儿子编号，需要注意的是儿子是有顺序的（有左右儿子之分）。
6. “多叉树枚举”。对于一个排列 (p) ，如果规定 (i) 的父亲节点是 (max {jmid j<iland p_j<p_i}igcap {0}) ，并且规定一个节点的儿子的顺序是按位置从小到大，那么就可以给这个排列构建出一棵儿子有顺序根为 (0) 的树，并且不难发现这样的树和排列是一一对应的，这棵树按儿子顺序 dfs 得到的 dfs 序恰好是排列 (p) ，并且这棵树满足一个点的编号要比排名比它小的兄弟和它的父亲大。

对于上述的第 4 点的排列个数的解释，首先假设置换是有标号的，那么方案数就是：

[{nchoose a_1,a_2,dots,a_k}prod_{i=1}^k(a_i-1)!=frac{n!}{prod_{i=1}^ka_i} ]

但是置换是没有标号的，所以方案数是：

[frac{n!}{prod_{i=1}^ka_iprod_{i=1}^nb_i!} ]

对于第 6 点，构建出来的树其实还有一种构造方法，就是对于每个 (i(1le ile n)) ，给 (i) 在 ([0,i-1]) 中选择一个父亲，并且规定儿子顺序（这里儿子顺序是按编号从大到小）后得到的树，并且构建出来得到的树“多叉转二叉”后其实就是笛卡尔树。

当然可能还会有其他枚举方法，我见到了大概（？）会放上来。