排序

Published: by Creative Commons Licence

  • 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(mn\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)$。