没有更多推荐了，
不良信息举报
举报内容：
卡特兰数---n 个元素顺序入栈，则可能的出栈序列有多少种
举报原因：
原文地址：
原因补充：
最多只允许输入30个字
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！为什么给定节点个数的二叉树个数为卡特兰数？ - 知乎26被浏览<strong class="NumberBoard-itemValue" title="分享邀请回答1添加评论分享收藏感谢收起出栈顺序 与 卡特兰数(Catalan)的关系
时间： 12:37:29
&&&& 阅读：75
&&&& 评论：
&&&& 收藏：0
标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&一，问题描述
给定一个以字符串形式表示的入栈序列，请求出一共有多少种可能的出栈顺序？如何输出所有可能的出栈序列？
比如入栈序列为：1 2 3& ，则出栈序列一共有五种，分别如下：1 2 3、1 3 2、2 1 3、2 3 1、3 2 1
二，问题分析
先介绍几个规律：
①对于出栈序列中的每一个数字，在它后面的、比它小的所有数字，一定是按递减顺序排列的。
比如入栈顺序为：1 2 3 4。
出栈顺序：4 3 2 1是合法的，对于数字 4 而言，比它小的后面的数字是：3 2 1，且这个顺序是递减顺序。同样地，对于数字 3 而言，比它小的后面的数字是： 2 1，且这个顺序是递减的。....
出栈顺序：1 2 3 4 也是合法的，对于数字 1 而言，它后面没有比它更小的数字。同样地，对于数字 2 而言，它后面也没有比它更小的数字。
出栈顺序：3 2 4 1 也是合法的，对于数字 3 而言，它后面比 3 小的数字有： 2 1，这个顺序是递减的；对于数字 2 而言，它后面的比它 小的数字只有 1，也算符合递减顺序；对于数字 4 而言，它后面的比它小的数字也只有1，因此也符合递减顺序。
出栈顺序：3 1 4 2 是不合法的，因为对于数字 3 而言，在3后面的比3小的数字有：1 2，这个顺序是一个递增的顺序(1--&2)。
因此，当给定一个序列时，通过这个规律 可以轻松地判断 哪些序列是合法的，哪些序列是非法的。
②给定一个入栈顺序：1& 2& 3 .... n，一共有多少种合法的出栈顺序？参考：
答案是 卡特兰数。即一共有：h(n)=c(2n,n)/(n+1) 种合法的出栈顺序。
如果仅仅只需要求出一共有多少种合法的出栈顺序，其实就是求出组合 C(2n,n)就可以了。而求解C(2n,n)，则可以用动态规划来求解，具体可参考：
三，代码实现
给定一个入栈顺序，比如 1 2 3 ，如何输出所有可能的出栈顺序？
思路①：先求出入栈顺序的所有排列（即全排列），并将排列保存到一个LinkedList&String&中，然后依次遍历每一个序列，判断该序列是否是合法的序列。
所谓合法的序列，就是满足上面的规律1：对于出栈序列中的每一个数字，在它后面的、比它小的所有数字，一定是按递减顺序排列的。 关于如何求解一个序列的全排列，可参考：
完整代码实现如下：（实现得不好，感觉比较复杂）
import java.util.C
import java.util.I
import java.util.LinkedL
public class AllStackPopOrder {
public static LinkedList&String& allPermutation(String str){
if(str == null || str.length() == 0)
return null;
//保存所有的全排列
LinkedList&String& listStr = new LinkedList&String&();
allPermutation(str.toCharArray(), listStr, 0);
//print(listStr);//打印全排列
return listS
private static void allPermutation(char[] c, LinkedList&String& listStr, int start){
if(start == c.length-1)
listStr.add(String.valueOf(c));
for(int i = i &= c.length-1; i++)
//只有当没有重叠的字符 才交换
if(!isSwap(c, start, i))
swap(c, i, start);//相当于: 固定第 i 个字符
allPermutation(c, listStr, start+1);//求出这种情形下的所有排列
swap(c, start, i);//复位
private static void swap(char[] c, int i, int j){
tmp = c[i];
c[i] = c[j];
private static void print(LinkedList&String& listStr)
Collections.sort(listStr);//使字符串按照‘字典顺序‘输出
for (String str : listStr) {
System.out.println(str);
System.out.println("size:" + listStr.size());
//[start,end) 中是否有与 c[end] 相同的字符
private static boolean isSwap(char[] c, int start, int end)
for(int i = i & i++)
if(c[i] == c[end])
return true;
return false;
public static LinkedList&String& legalSequence(LinkedList&String& listStr){
Iterator&String& it = listStr.iterator();
String currentS
while(it.hasNext())//检查全排列中的每个序列
currentStr = it.next();
if(!check(currentStr))
it.remove();//删除不符合的出栈规律的序列
return listS
//检查出栈序列 str 是否 是合法的出栈 序列
private static boolean check(String str){
boolean result = true;
char[] c = str.toCharArray();
char//当前数字.
int k = 0;//记录 compare 数组中的元素个数
char[] compare = new char[str.length()];
for(int i = 0; i & c. i++)
first = c[i];
//找出在 first 之后的，并且比 first 小的数字
for(int j = i+1; j & c. j++)
if(c[j] & first)
compare[k++] = c[j];//将比当前数字小的 所有数字 放在compare数组中
if(k == 0)
for(int m = 0; m & k-1; m++)//判断 compare 数组是否是 递减的顺序
if(compare[m] & compare[m+1])
result = false;//不符合递减顺序
//hapjin test
public static void main(String[] args) {
String str = "1234";
LinkedList&String& listStr = legalSequence(allPermutation(str));
print(listStr);
思路②：直接求出合法的出栈序列。【而不是像思路①那样：先求出所有可能的出栈序列(求全排列)，然后再找出合法的出栈序列。】
四，参考资料
标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&原文：http://www.cnblogs.com/hapjin/p/5758083.html
教程昨日排行
&&国之画&&&& &&&&&&
&& &&&&&&&&&&&&&&
鲁ICP备号-4
打开技术之扣，分享程序人生！栈的输入序列依次为1，2，3，4，则不可能的出栈序列是
[问题点数：20分，结帖人lantianhanerqiang]
栈的输入序列依次为1，2，3，4，则不可能的出栈序列是
[问题点数：20分，结帖人lantianhanerqiang]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
2012年5月 专题开发/技术/项目大版内专家分月排行榜第二2010年3月 C/C++大版内专家分月排行榜第二
2012年4月 Linux/Unix社区大版内专家分月排行榜第三2011年7月 Linux/Unix社区大版内专家分月排行榜第三2010年2月 C/C++大版内专家分月排行榜第三
匿名用户不能发表回复！|zz出栈序列统计（组合数学卡特兰数，好吧我又弱了）
栈是一种常见的数据结构，有许多关于栈的问题，其中之一就是统计元素可能的出栈序列。具体说，就是给定n个元素，依次通过一个栈，求可能的出栈序列的个数。
如果我们用直接模拟的方法，当n较大时会很费时间；另一种方法是利用组合数学求出栈序列个数，得到公式
下面我们来看一种图形化的方法证明这个等式，很容易理解的。
我们把对n个元素的n次进栈和n次出栈理解为在一个n&*&n的方格中向右走n次（代表进栈），向上走n次（代表出栈）。由于出栈次数不能大于进栈次数，我们可以得到这样一个方格：
&&&&&&&&每次沿着实线走，所以，只要求出从方格左下角到右上角路径的个数即可。
&&&&&&&&我们把表格补全，考虑每一条不合法的路径，如
&&&&&&&&在这条路径上，必然有一个地方连续两次向上，即从图上蓝点处开始，而且这个点必然在如图所示的绿线上。我们以这个点为起点，把到左上角整条路经取反，也就是对称上去，得到一条新路径，但是超出了表格。我们知道，这条路径包括n&+&1次向上和n&&&1次向下，也就是在一个(n&+&1)&*&(n&-&1)的方格中。由此我们知道，一条不合法路径必然对应一个(n&+&1)&*&(n&-&1)方格中的路径。同样地，对于(n&+&1)&*&(n&-&1)方格中任意一条路径，以这条路径与绿线的第一个交点为起点到方格的右上方全部取反，即可得到一个在n&*&n方格中的不合法路径。
&&&&&&&&我们通过这样的方法确定了每条不合法路径与一个(n&+&1)&*&(n&-&1)方格中路径的一一对应关系，因此，方格中不合法路径总数为C(2n,&n&-&1)，而所有路径总数为C(2n,&n)，两式相减即为原组合等式。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。}