合法栈输出队列的充要条件
问题背景
Algorithm 4th (Robert Sedgewick, Kevin Wayne) 一书中有这样一道习题:
1.3.46 Forbidden triple for stack generability. Prove that a permutation can be gener- ated by a stack (as in the previous question) if and only if it has no forbidden triple (a, b, c) such that a < b < c with c first, a second, and b third (possibly with other intervening integers between c and a and between a and b).
翻译成中文,可以理解为:请证明:如果一个栈的出栈顺序合法,当且仅当不存在这样的 forbidden triple:在序列中编号 c 后有编号 a、b,其中 c和a, a和b可以有间隔,而且 a < b < c。
定理描述
对于任意一个栈,假设其入栈编号分别从 1 到 n,其出栈顺序编号分别为 p1 到 pn。那么
一个合法的出栈顺序编号当且仅当对任意的 pm (m >= 1 且 m < n),从 pm+1开始,所有小于 pm 的子串严格单调递减。
这个定理通俗的描述是,一个合法的出栈顺序,对于任意一个编号,随后所有小于这个编号的部分是严格单调递减的。反过来也成立。
例如,下面这个入栈序列
1 2 3 4 5
的一个两个出栈序列
- 3 2 1 5 4
- 3 1 2 5 4
第一个是合法的,第二个是不合法的,因为比编号 3 小的随后的两个数 1 2 是递增的。
算法的证明
本文仅给出一个简略的证明方法。假设在出栈过程中,在某一个步骤时,栈中存留的元素有 n 个,分别是 s1 到 sn。
此时,对于元素 sn,有两种可能性。
1)在下一步时,可以选择弹出 sn。那么,比 sn 小的所有元素,只有两种可能:
a. 还未出栈(不可能还未入栈,因为比它大的元素 sn 已经入栈了):则一定在 sn 后以递减的顺序出现在出栈队列中(因为入栈的顺序是严格递增的)
b. 已经出栈:此时,比这个元素还小的元素如果还没出栈,当它即将出栈的时候,就会又递归回到1)的情况。
2)可以不弹出 sn 而是继续入栈,则又回到 1)的情况。
综上所属,对于这个元素 sn,其后续元素一定是单调递减的。
原书的证明
原书给出的部分证明如下。
Partial solution: Suppose that there is a forbidden triple (a, b, c). Item c is popped before a and b, but a and b are pushed before c. Thus, when c is pushed, both a and b are on the stack. Therefore, a cannot be popped before b.
更多的证明和参考材料
栈序列及其生成算法(郑州大学学报)Vol33,No 4,Dec 2001
题外话:我帮你整理了包括 AI 写作、绘画、视频(自媒体制作)零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效,辅助工作和生活?限时报名。
© 转载需附带本文链接,依据 CC BY-NC-SA 4.0 发布。