合法栈输出队列的充要条件

问题背景

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

的一个两个出栈序列

  1. 3 2 1 5 4
  2. 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 工具来降本增效,辅助工作和生活?限时报名

当前页阅读量为: