出栈顺序与卡特兰数(Catalan)的关系-白红宇

一，问题描述

给定一个以字符串形式表示的入栈序列，请求出一共有多少种可能的出栈顺序？如何输出所有可能的出栈序列？

比如入栈序列为：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.Collections;import java.util.Iterator;import java.util.LinkedList;public class AllStackPopOrder {                public static LinkedList
      
        allPermutation(String str){        if(str == null || str.length() == 0)            return null;        //保存所有的全排列        LinkedList
       
         listStr = new LinkedList
        
         ();                allPermutation(str.toCharArray(), listStr, 0);                //print(listStr);//打印全排列        return listStr;    }            private static void allPermutation(char[] c, LinkedList
         
           listStr, int start){        if(start == c.length-1)            listStr.add(String.valueOf(c));        else{            for(int i = start; 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){        char tmp;        tmp = c[i];        c[i] = c[j];        c[j] = tmp;    }        private static void print(LinkedList
          
            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 = start; i < end; i++)        {            if(c[i] == c[end])                return true;        }        return false;    }        public static LinkedList
           
             legalSequence(LinkedList
            
              listStr){ Iterator
             
               it = listStr.iterator(); String currentStr; while(it.hasNext())//检查全排列中的每个序列 { currentStr = it.next(); if(!check(currentStr)) it.remove();//删除不符合的出栈规律的序列 } return listStr; } //检查出栈序列 str 是否 是合法的出栈 序列 private static boolean check(String str){ boolean result = true; char[] c = str.toCharArray(); char first;//当前数字. int k = 0;//记录 compare 数组中的元素个数 char[] compare = new char[str.length()]; for(int i = 0; i < c.length; i++) { first = c[i]; //找出在 first 之后的，并且比 first 小的数字 for(int j = i+1; j < c.length; j++) { if(c[j] > first) continue; else { compare[k++] = c[j];//将比当前数字小的 所有数字 放在compare数组中 } } if(k == 0) continue; else{ for(int m = 0; m < k-1; m++)//判断 compare 数组是否是 递减的顺序 { if(compare[m] < compare[m+1]) { result = false;//不符合递减顺序 return result; } } } k=0; } return result; } //hapjin test public static void main(String[] args) { String str = "1234"; LinkedList
              
                listStr = legalSequence(allPermutation(str)); print(listStr); }}

View Code

思路②：直接求出合法的出栈序列。【而不是像思路①那样：先求出所有可能的出栈序列(求全排列)，然后再找出合法的出栈序列。】

待完成。

四，参考资料

本文转自hapjin博客园博客，原文链接：http://www.cnblogs.com/hapjin/，如需转载请自行联系原作者