栈混洗

栈混洗

三个栈，两种操作。 对于长度为 n 的序列，栈混洗总数 $SP(n)=?$ 事实上，$SP(n)$ 等于卡特兰数，每一时刻，A 操作次数必然大于等于 B 操作次数。 对于 $SP(n)$，考虑第 1 位在混洗后位于哪个位置，先进行一次 A 操作： 有 n 种情况，对于第 k 种情况，相当于先对前 k-1 位进行混洗，将第 1 位插入，再对后 n-k 位进行混洗。

$$SP(n)=\sum _{i=1}^{n}SP(k-1)\cdot SP(n-k)=\frac{(2n)!}{n!\cdot (n+1)!}$$

检测禁形

1. 禁形：对任何 $1\le i<j<k\le n$，$[\dots ,k,\dots ,i,\dots ,j,\cdots >$ 必然不是栈混洗。一个序列是栈混洗当且仅当它不含禁形。枚举 $i,j,k$，可以得到 $O(n^3)$ 的检测算法。
2. 事实上，对任何 $1\le i<j\le n-1$，$[\dots ,j+1,\dots ,i,\dots ,j,\cdots >$ 必然不是栈混洗。不存在这样的禁形也是一个序列是栈混洗的充要条件。枚举 $i,j$，可以得到 $O(n^2)$ 的检测算法。
3. 直接模拟：逐个检视 B 中目标元素，若在 S 栈顶，则执行 B 操作，若在 S 中却并非栈顶，则不是栈混洗。时间复杂度为 $O(n)$。 A 操作不少于 B 操作，左括号不少于右括号，实际上，n 个元素的栈混洗一一对应于 n 对括号的所有可能匹配的表达式。