排序

Published: December 03, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 链和反链
• 整除偏序关系
• 字符串无穷偏序
• 拓扑序问题
• 排序操作
• 基础排序算法
  • 冒泡排序

链和反链

对于偏序集$S$，称$S$的子集$A$是链，当且仅当$A$组成一个全序集。若$S$的子集$B$中元素两两不可比较，那么称$B$是反链。

最小链覆盖是指$S$的一个子集族，每个元素都是链，所有元素的并为$V$，但是不同元素的交集为空。同样最小反链覆盖也是$S$的一个子集族，每个元素都是反链，所有元素的并为$V$，但是不同元素的交集为空。

Dilworth定理：偏序集的最小链覆盖大小等于S的最长反链的长度

证明：

记最小链覆盖的大小为$n$，最长反链长度为$m$。

设$L$是$S$的一个最长反链，很显然多个$L$中的元素不能同时属于相同的链，因此最小链覆盖至少包含$m$个链，即$n\geq m$。

之后利用数学归纳法证明$n\leq m$。

当S的大小为$0$或$1$的时候，命题显然成立。

我们记$s$是$S$的一个极大元，记$S'=S-\left\{s\right\}$。由归纳法知，$S'$的最小链覆盖的大小与最长反链的长度相同，记作$k$。设$S'$的最长链覆盖为${C_1, C_2, \ldots, C_k}$，而$S'$的所有长度为$k$的反链为$R_1, R_2, \ldots, R_r$。很显然，对于$R_i$，必定是由最长链覆盖中每个集合取一个元素组成的，我们记$R_i$与$C_j$的唯一公共元素为$x_{ij}$。对于$j=1,2,\ldots, k$，记$m_j=\max_i(x_{ij})$。现在考虑集合$M={m_1, m_2, \ldots, m_k}$，如果其中有任意两个不同元素$m_i,m_j$可以比较，不妨设$m_i\leq m_j$，记$m_i$所在的反链为$R_p$，而$m_j$所在的反链为$R_q$，那么可以推出$x_{qj} = M_j \geq x_{pi} = M_i \geq x_{qi}$，即$R_q$包含两个可比较元素，这是不可能的，因此我们知道$M$是反链。

接下来我们考虑集合$S$，即向$S'$加入元素$s$。考虑两种情况：

1) 如果$M$与$s$中元素都不可比较，那么我们考虑集合$M\cup {s}$，这是一个长度为$k+1$的反链。而向集合中加入一个元素，最多会增加其最长反链长度$1$，以及最小链覆盖大小$1$。因此有$m\geq k+1 \geq n$。

2) 如果$M$与$s$中某个元素可以比较，假设$s$与$M_i$可以比较，设$M_i$所在的反链为$R_j$，那么我们可以推出$s$大于等于$R_j$中的所有元素，即$D=R_j\cup {s}$也是一个链。现在考虑集合$S''=S-D$，由于$S$中的所有反链都少了一个元素，因此$S''$的最长反链的长度为$k-1$，同样利用归纳法知其最小链覆盖为$\left\{C'_1,C'_2,\ldots, C'_{k-1} \right\}$。我们将D加入得到新的最小链覆盖$\left\{C'_1,C'_2,\ldots, C'_{k-1}, D\right\}$。因此$S$的最小链覆盖大小一定是$k$，故可以得到$m\geq k = n$。

Dilworth对偶定理：偏序集的最小反链覆盖大小等于$S$的最长链长度

证明：

记最小反链覆盖的大小为$n$，最长链长度为$m$。

设$L$为$S$的一个最长链，而$L$中多个元素肯定不能同时属于一个反链，因此最小反链覆盖至少含有$m$个反链，即我们推出了$n\geq m$。

我们记$X_1$为$S$中的极小元的集合，并从$S$中移除$X_1$的元素。之后继续定义$X_2$为S中极小元的集合，并同样从中移除。重复这个过程，直到$S$为空，假设过程中我们得到了$k$个非空集合$X_1,X_2,\ldots, X_k$。极小元的集合一定是$S$的一个反链，我们得到了一个大小为$k$的反链覆盖。同样我们从$X_1,X_2,\ldots, X_k$中分别取一个元素$x_1,x_2,\ldots, x_k$，满足$x_1\leq x_2 \leq \ldots \leq x_k$，这样我们就得到了长度为k的一个链。得到关系式$n\geq k \geq m$，结合之前得到的$n\geq m$，可以推出$n=m$。

求最长反链方法：

我们先利用最小相交路径覆盖将图建成二分图并求得最大匹配。设$n$为顶点数，最大匹配数为$m$，记$l(i)$表示二分图左侧第$i$个顶点，$r(i)$表示二分图右侧第$i$个顶点。

之后我们可以找到最小顶点覆盖，利用最小顶点覆盖得到最大独立集。对于$1\leq i \leq n$，如果$l(i)$和$r(i)$同时属于最大独立集，我们就将它放入到集合$A$中，集合$A$初始时为空集。在上述操作后，我们得到的集合$A$就是最长反链条。上面的算法的时间复杂度为$O(n^{2.5})$。

用反证法证明，如果$A$中任意两个元素$u$、$v$可比较，那么不妨设$u\leq v$。这意味着$l(u)$与$r(v)$之间有边，而我们知道$l(u),r(u),l(v),r(v)$都属于最大独立集，因此不可能发生。

现在我们证明得到的反链长度正好为$n-m$。由于二分图共有$2n$个顶点，而最大独立集中有$2n-m$个顶点。$|最大独立集|=|A|+|\left\{i|l(i)与r(i)有且仅有一个属于最大独立集\right\}|$。而后者最多为$n$，因此推出前者至少为$n-m$。当然反链长度是不可能超过$n-m$的，因此得到的反链的长度恰好为$n-m$。

整除偏序关系

对于两个正整数$a,b$，如果$a\mid b$，则认为$a\prec b$。很显然这是一个偏序关系。

题目1：要求找到$1$到$n$的所有整数的最长链。

由算术基本定理可知，最长链等价于找到一个数$x$，满足$1\leq x\leq n$，并且其分解后素因子的幂次和最大。我们可以直接找最大的数$2^m$，满足$2^m\leq n$，则最长链的长度为$m+1$，且最长链为$2^0,2^1,\ldots,2^m$。

题目2：要求找到$1$到$n$的所有整数的最小反链覆盖。

提供一道题目。

记$m=\left\lfloor \log_2n \right\rfloor$，很显然由于$2^0,2^1,\ldots,2^m$的存在，它们需要分到不同的组中，因此至少需要分成$m+1$组。

下面我们给出一个将$n$个数正好分成$m+1$组的算法。根据算术基本定理，我们知道对于任意正整数$x$，有$x=p_1^{c_1}p_2^{c_2}\ldots p_k^{c_k}$，我们可以记$\mathrm{deg}(x)=\sum_i c_i$。之后我们将数$x$分类到第$\mathrm{deg}(x)+1$组即可。由于对于任意数$1\leq x\leq n$，都一定有$0\leq \mathrm{deg}(x)\leq m$，因此最多只需要分成$m+1$组。

这里顺带一提，贪心算法得出的分组结果和上面的方案是相同的。

上面的做法是$O(n\ln n)$的，但是如果我们将$x$分组到$\left \lfloor \log_2x \right\rfloor+1$组的话，可以$O(n)$进行分组。

字符串无穷偏序

对于字符串$S$，记$S^+$表示无穷个$S$前后拼接得到的无穷长的字符串。

命题1：对于任意字符串$A,B$，$A^+\leq B^+ \Leftrightarrow AB\leq BA$，这里的比较规则是字典序。

证明：

如果$A$与$B$相互没有前缀关系，则命题很显然成立。下面不妨假设$A$是$B$的前缀，换言之，$B=AC$。

考虑到$A^+$和$B^+$的大小关系由其长度为$m=|A||B|$的前缀共同确认，因此我们只需要保证这一段前缀中$A^+$和$B^+$的关系即可。

如果$AB\leq BA$成立。那么容易推出$AC\leq CA$，之后我们有

$$\begin{aligned} B^+&=(AC)^+\\ &=A(CA)^+\\ &\geq A(AC)^+\\ &=A^2(CA)^+\\ &\ldots\\ &\geq A^{|B|}(AC)^+\\ \end{aligned}$$

由于$B^+$的长度为$m$的前缀字典序不小于$A^+$，因此有$A^+\leq B^+$。

同理如果$AB> BA$成立，可以推出$A^+>B^+$。

至此命题得证。

题目1：给定$n$个字符串，要求将这些字符串按照一定的顺序拼接起来，且要求拼接得到的字符串字典序最小。

提供一道题目。

假设结果中$A$和$B$相邻，且$A$在$B$之前，则很显然有$AB\leq BA$成立（否则我们可以交换两者的顺序得到更小字典序的结果）。考虑到$AB\leq BA$等价于$A^+\leq B^+$，而后者是全序关系，因此可以直接上排序算法。时间复杂度为$O(nm\log_2n)$，其中$m$为字符串长度。

拓扑序问题

给定一副有向无环图，并给所有顶点排序，满足如果存在边$(u,v)$，则$u$的序号大于$v$的序号，那么称这个序列满足拓扑序。

题目1：生成某个$n$个顶点$m$条边的有向无环图的任意拓扑序。

可以不断地删除出度为$0$的顶点，这样就能的到满足条件的拓扑序。可以用队列维护所有度数为$0$且未被删除的顶点，时间复杂度为$O(n+m)$。

题目2：生成某个$n$个顶点$m$条边的有向无环图的字典序最小的拓扑序。

在题目1的基础上，不断从队列中删除编号最小的顶点即可。可以将队列替换为优先队列，这样就可以得到$O(n\log_2n+m)$的时间复杂度性能。

题目3：生成某个$n$个顶点$m$条边的有向无环图的某个拓扑序，要求保证$1$的序号最小，如果有多个，则保证$2$的序号最小，如此循环下去。

提供一道题目。

考虑生成最小字典序的时候，我们贪心删除编号最小的字典序。这时候实际上等价于我们要让编号较大的顶点序号尽可能大。现在我们希望让编号较小的顶点序号尽可能小，我们可以尝试生成一个反向拓扑序，且要求这个反向拓扑序的字典序最大即可。可以用类似题目2的做法来做，时间复杂度为$O(n\log_2n+m)$。

排序操作

给定长度为$n$的序列，以及$k$个函数$f_1,\ldots,f_n$，其中每个函数会对输入序列的某个子序列进行排序。要求判断对于任意给定序列$x$，能否保证$f_n(f_{n-1}(\cdots f_1(x)\cdots ))$返回的序列是有序的。

问题1：给定长度$n$和$m$个命令，判断是否对于所有长度为$n$的序列，执行上述$m$个命令后都能得到有序序列。命令从前往后执行，每个命令指定若干个位置，将这些位置的数从小到大进行重排。其中$n\leq 15$，$m\leq 100$。

我们不能枚举所有的$n$种排列，因为数量级太大。但是我们可以这样玩，我们考虑一个长度为$n$的01序列，其中部分为1，部分为0。如果命令能保证对所有长度为$n$的序列正确排序，那么自然也能对我们的$01$序列进行排序。

现在我们断定如果所有可能的长度为$n$的二进制序列经过排序后都是有序的，那么一定能正确排序所有的长度为$n$的序列。用反证法，假设存在一个序列$a$不能被正确排序，那么考虑在对$a$应用$m$个命令后得到的新序列为$b$，考虑最小的数$x$，满足存在某个更小的数在$b$中排在$x$后面。接下来，我们将$a$中所有大于等于$x$的数改写为$1$，而所有小于$x$的数改写为$0$，那么经过$m$个命令后，得到的新序列实际上是将$b$中所有大于等于$x$的数改成$1$，而其余数改写为$0$，这样我们就发现一个长度为$n$的二进制序列不能被正确排序，这与前提相悖。

用这种方式做校验，时间复杂度为$O(mn2^n)$。

提供一道题目：SRM761 SortArray。

问题2：给定长度$n$和$m$个命令，判断是否对于所有长度为$n$的序列，执行上述$m$个命令后都能得到有序序列。命令从前往后执行，每个命令指定若干个位置，将这些位置的数从小到大进行重排。其中$n\leq 60$，$m\leq 10$。

提供一道题目。

题目1的做法在这里不适用，但是我们可以借鉴它通过对所有二进制串排序的校验方式。

如果$n=1$，很显然所有指定都是能保证正确排序的。下面考虑$n>1$的情况。

令$N=\left\{1,2,\ldots,n\right\}$。

记第$i$个命令指定的下标集合为$I_i$，记$S_i=\bigcup_{j=1}^iI_j$。很显然指令能正确重排的前提是$S_m=N$。

我们考虑一个函数$f:S_i\rightarrow \left\{0,1\right\}$。我们称函数$f$是$i$可达的，当且仅当存在一个01序列$b_1,\ldots,b_n$，经过前$i$个命令处理后，对于$j\in S_i$，有$f(j)=b_j$。

那么我们可以得到我们排序算法成立的充要条件，所有$m$可达的函数都是递增函数，而这样的函数最多只有$n+1$个。我们可以通过枚举所有可能的$m$可达函数来校验我们的排序算法是否有效。

我们记$D_i=S_i\setminus S_{i-1}$，令$S_0=\emptyset$。那么当我们执行完前$i-1$个命令后，要处理第$i$个命令时，实际上真正会影响结果的只有输入二进制串$D_i$位置上的$1$的数目，它只有$|D_i|+1$种可能。

因此我们暴力枚举的时间复杂度为$O(\prod_{i=m}^n|D_i|+1)$。由于$|D_1|+1+\ldots+|D_m|=n+m$，因此有上界$O((\frac{n+m}{m})^m)$。

这里我们需要使用二进制来表示集合，以及利用它快速计算交集并集等操作，否则时间复杂度需要额外乘上一个$n$。

基础排序算法

冒泡排序

要排序大小为$N$的数组$A$。循环下面流程直到整个数组有序

• 顺序枚举$i=0,1,\ldots,N - 2$，如果$A_i>A_{i+1}$，则交换两个数。

很显然冒泡排序一定会结束（每次都至少减少一个逆序对），且最终数组一定有序。

下面分析一下冒泡排序的原理：

考虑另外一个大小为$N$的数组$B$，其中$B_i$表示$A_0,\ldots,A_{i-1}$中比$A_i$大的数的个数。很显然$B_i\leq i$。如果$A$是一个置换，不难发现$A$与$B$有唯一对应关系（可以$O(N\log N)$的时间复杂度内相互转换。当$A$有序的时候，$B$的所有元素都是$0$。

考虑一次冒泡排序的循环体，其本质上做的事情是：

1. 对于$i=0,\ldots,N-1$，将$B_i$修改为$\max(B_i-1,0)$。
2. 将数组$B$循环左移一步，即新的数组为$B_1,\ldots,B_{N-1},B_0$。

因此我们直接操作$B$的话，可以快速模拟出$A$经过$k$次冒泡后的排列。同时只需要经过$\max B$次冒泡整个数组有序。