出栈序列与卡特兰数

Posted on Edited on In Views:
Symbols count in article: 2.7k Reading time ≈ 2 mins.
对于按一定顺序入栈的元素序列，研究其所有可能的出栈顺序。

出栈序列与卡特兰数

问题

有n个元素组成的序列，如a, b, c, ......，顺序入栈（入栈元素的顺序符合这个序列即可），入栈操作之间可以有出栈操作，也就是可以a入栈、b入栈、b出栈……

有以下问题：

  • 所有可能的出栈序列有多少种？
  • 判断一个序列是否是可能的出栈序列。
  • 对于有n个元素的元素序列S，依次入栈，输出所有可能的出栈序列。

分析

假设元素序列为a, b, c, d, ..., z。

n = 1时，所有可能的出栈序列只有{ "a" }，共1种；

n = 2时，所有可能的出栈序列只有{ "ab", "ba" }，共2种；

n = 3时，所有可能的出栈序列只有{ "abc", "acb", "bca", "bac", "cba" }，共5种；

由于栈的后进先出（LIFO）特性，所有可能的情况必然不是全排列的种数，因而我们从栈的特性开始分析。

毫无疑问，第一个入栈的元素必然为0号元素。但是最后一个出栈的元素是不定的。

为什么呢？

对于k号元素来说，如果它最后一个出栈，则1 ~ k-1号元素肯定在它入栈之前就全部出栈，k+1 ~ n号元素肯定在它出栈之前全部出栈，这对于\(\forall k=1,2,...,n\)成立。因此最后一个出栈的元素可以是任意一个。

需要注意的是，我们在出栈序列与入栈元素序列之间建立了一种对应关系：

graph LR
    subgraph 入栈元素序列
    A["1 ~ k-1"]
    B["k"]
    C["k+1 ~ n"]
    end
    subgraph 出栈序列
    D["1 ~ k-1"]
    E["n"]
    F["k ~ n-1"]
    end
    A --> D
    B --> E
    C --> F

注意：这种对应关系对于出栈序列的任意一个前缀子序列都成立。

由于上述这样一种递归关系，我们可以这样分析：

  • \(n\) 个元素的元素序列，假设 \(f(n)\) 为所有可能的出栈序列种数。
  • 序列的编号为：\(1\sim n\)。
  • 设最后出栈的元素为元素序列的 \(k\) 号元素，\(k\) 取不同值，出栈序列的情况是相互独立的。
  • 元素序列 \(1\sim k-1\) 与 \(k+1\sim n\) 号元素的入栈出栈序列是相互独立的。
  • 则：\(f(n)=\sum_{k=1}^{n}f(k-1)f(n-k),\;f(0)=1\)

这就是卡特兰（Catalan）数。

它的递推式有： \[ f(n)=f(n-1)\cdot\frac{4n-2}{n+1}\;(n=1,2,...,n),\;f(0)=1 \]

\[ f(n)=\sum_{k=1}^{n}f(k-1)f(n-k)\;(n=1,2,...,n),\;f(0)=1 \]

它的解有： \[ h(n)=\frac{C_{2n}^n}{n+1}\;(n=0,1,2,...) \]

\[ h(n)=C_{2n}^n-C_{2n}^{n-1}\;(n=0,1,2,...) \]

递推式（1）即递推式的解摘自百度百科。

C语言代码

对于所有可能的出栈序列的种数问题已经解决了，那么如何判断一个序列是不是可能的出栈序列呢？

思路还是和我们的分析一致，就是检查每一个前缀子序列，看它是否满足如下两个条件：

  1. 在待判断序列中存在一个“位置”，使得在该位置之前的元素，它们的“标号”均小于待判断序列最后一个元素的“标号”；
  2. 在该位置之后的元素，它们的“标号”均大于等于待判断序列最后一个元素的“标号”；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int Seq_Pop_Stack_N(char *S, char *T, int n){
	int End = 1;
	if(n < 3) return End;
	int *temp_T = (int *)malloc((n + 1) * sizeof(int));
	temp_T[0] = -1;
	int i, j;
	// 将带判断的出栈序列转换成各个元素下标的序列 
	// 各元素下标的序列temp_T开头元素为-1，小于任何下标 
	for(i=0;i<n;i++){
		j = 0;
		while(S[j] != T[i]) j++;
		temp_T[i+1] = j;
	}
	//for(i=0;i<n+1;i++) printf("%d ", temp_T[i]);
	//printf("\n");
	for(i=2;i<n;i++){
		j = 0;
		while(temp_T[j] < temp_T[i+1]) j++;
		//printf("[divide] %d\n", j - 1);
		while(temp_T[j] > temp_T[i+1]) j++;
		//printf("[end] %d\n", j - 1);
		if(j == i + 1) continue;
		else{
			End = 0;
			break;
		}
	}
	return End; 
}

int main(){
	char S[] = "abcd";
	//char T[] = "abdc";
	char* Test_1[] = {"adbc","bdac","cabd","cadb","cdab", \
					"dabc","dacb","dbac","dbca","dcab"};
	char* Test_2[] = {"dcba","cdba","cbda","cbad","bdca","bcda","bcad",\
					"badc","bacd","adcb","acdb","acbd","abdc","abcd"};
	for(int i=0;i<10;i++){
		printf("Test_1(%s) = %d\n\n", Test_1[i], Seq_Pop_Stack_N(S, Test_1[i], 4));
	}
	//printf("%d\n", Seq_Pop_Stack(S, T, 4));
	return 0;
}