栈混洗概念、甄别（栈的应用一）

栈混洗概念、甄别（栈的应用一）

//最近听邓俊辉老师的课学数据结构，在这里对学到的知识做一些比较详细易懂的整理、梳理。

栈混洗 stack shuffle/stack permutation

概念：将栈A的顶元素弹出并压入栈S，或将栈S的顶元素弹出并压入栈B中，经过一系列的操作后，A中元素全部转入B中，则称之为A的一个栈混洗。这里标记  尖括号<：栈顶，方括号 ] ：栈底 ，两个栈的弹出与压入次序不一样由此产生了在B栈的不同排序方式。

栈混洗的计数:

例如A:1 2 3的混洗结果可能有 123，132，213，231，321，不可能出现312 (原因如下图右上角）

经观察，任意三个元素出现的排序方式与其他元素无关，如果出现了 k i j 的排序方式，必定不是栈混洗的结果——充要条件

如果不出现312 的模式（ j+1,i,j ）那必然是栈混洗的结果,312模式称之为禁形。

栈混洗的甄别

 甄别方法有三种思路：

1. 不断枚举i,j,k的组合 复杂度 O（n^3&