应用卡塔兰数解决出栈分析

今天被一道数据结构习题难住了，觉得挺有意思就写博一篇记录下来，被该题男主并非是不会用编程解决，而是考虑问题思维太狭窄导致的。

 

题目如下：

 

铁路进行列车调度时, 常把站台设计成栈式结构的站台。试问：

设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?

 

 

本题题意是，给定一组入栈顺序，可在任意时刻任意出栈，求有多少种出栈方式。

看到题目瞬间就想当然认为是暴力枚举求解这道题，再一看答案，居然是用排列组合解出这道题的，不禁引诱我重新认真思考这道题。

 

 

经过长时间的思考和搜索资料，终于了解到这个题目是用一种叫做：卡塔兰数 的组合数求解的。

 

本问题可以转换为：

对一个2n长度的位串，其中有n个"1"，n个"0"，从左到右扫描时，"0"出现次数不能比"1"多（第一次出现"0"也作为非法位串）。

 

所以非法情况可以设为：

前2m+1次扫描中，出现了m+1次"0"，m次"1"（此处m为小于n/2-1的任意非负整数），此时可确定该组合情况是错误情况，并且存在：后2n-2m-1次操作中，有n-m次"1"，n-m-1次"0"，此时可进一步分析，假设n-m个"1"与n-m-1个"0"互换，则总共变成了n+1个"0"和n-1个"1"。

 

此时我们猜想：

是否可以设想例外情况就是对n+1个"0"和n-1个"1"的组合？

进一步分析该猜想，对于此组合，"0"的个数比"1"多2个，则必有扫描时，第一次出现"0"的个数大于"1"的个数时，其后位串的所有"1"和"0"数目交换，则最终整个位串变成n个"1"和n个"0"的排序，并且该排序就是我们要找的非法排序。

 

归纳：

由于n+1个"0"和n-1个"1"的组合数可以与例外排序一一映射，所以我们的例外情况总数为：

所以，最终总数为：

 

 

 

 

 

PS：

 

卡塔兰数--wiki

 

卡塔兰数应用丰富，在计算机领域应用很广泛，比如：

 

• 表示有n个节点组成不同构二叉树的方案数。
• 表示有2n+1个节点组成不同构满二叉树
• 表示n个元素依次入栈的出栈顺序数
• ……