| title | date | draft | tags | categories | |||
|---|---|---|---|---|---|---|---|
Algorithm4 Java Solution 1.3.46 |
2019-07-28 08:47:27 +0800 |
false |
|
|
Forbidden triple for stack generability. Prove that a permutation can be generated 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).
栈可生成性问题中禁止出现的排列。不含这样的三元组(a,b,c)，c是第一个，a是第二个，b是第三个。 a < b < c。
code:
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.
a b 会在 c 之前被压入，当c弹出时，a b 还在栈中，所以 a 不能在 b 之前被弹出