合法棧輸出隊列的充要條件

問題背景

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

關於棧輸出序列的問題補充