[人工智能]【数据结构与算法/组合数学】出栈序列的个数问题详解

假设有一个入栈序列$a_1,a_2,?,a_n$，现在求它有多少种出栈序列。

例如，对于入栈序列$1,2,3$，我们有$5$种出栈序列：
$①3,2,1$：push 1,push 2,push 3,pop 3,pop 2,pop 1
$②2,3,1$：push 1,push 2,pop 2,push 3,pop 3,pop 1
$③1,3,2$：push 1,pop 1,push 2,push 3,pop 3,pop 2
$④1,2,3$：push 1,pop 1,push 2,pop 2,push 3,pop 3
$⑤2,1,3$：push 1,push 2,pop 2,pop 1,push 3,pop 3

现在我们考虑对任意$n$的情况。令$f(i)$代表长度为$i$的序列的出栈序列个数。则我们要求的就是$f(n)$。

显然，$f(0)=f(1)=1$，因为没有元素和只有一个元素的时候都只有一种顺序。有$n$个元素时，问题太大，我们采用分而治之的思想，递归求解。考虑入栈的第一个元素$a_1$在出栈序列中的位置。设$a_1$是第$j$个出栈的，则$a_2～a_j$必须在$a_1$之前出栈。这个性质是十分关键的。要理解这个性质，必须运用栈的LIFO (Last In First Out)（后进先出）特征。因为$a_2～a_j$比$a_1$后入栈，那就比$a_1$先出栈。换句话说，$a_2～a_j$一定是压在$a_1$头顶的，如果它们不出去，$a_1$就没法出去。当$a_1$出去时，栈一定是空的。那么下面就简单了。现在$a_1$把出栈序列分割为两部分：$a_2～a_j$，$a_{j+1}～a_n$。我们看到，前一部分和后一部分是相互独立的。而前一部分的出栈顺序个数为$f(j?1)$，后面一部分的出栈顺序个数为$f(n?j)$。因为二者互不影响，所以贡献的总出栈顺序个数为$f(j?1)\times f(n?j)$。如果你不理解，可以先考虑前一部分有一个固定的顺序，那么后一部分有$f(n?j)$种顺序；再令前一部分的顺序变化，共有$f(j?1)$种变化，所以结果就是$f(j?1)$个$f(n?j)$，即$f(j?1)\times f(n?j)$。好了，这就是对于一个固定的$j$的顺序个数。再令$j$取到$1～n$，用加法原理把所有可能性加起来，就是$$\begin{array}{rl}f(n)& =f(0)f(n?1)+f(1)f(n?2)+?+f(n?1)f(0)\\ & =\sum _{j=1}^{n}f(j?1)f(n?j)\end{array}$$这里要求$n\ge 2$。这个递推公式解起来挺麻烦的，我们直接给出结论。事实上，$f(n)$就是卡特兰数（Catalan Numbers），记作$C_n$（不要与组合数混淆QwQ），它的的公式是$$C_n=\frac{(2n)!}{(n+1)!n!}=\frac{1}{n+1}{C}_n^{2n}$$可以验证它满足我们推出的递推公式。当$n=3$时，$C_3=\frac{6!}{4!3!}=\frac{720}{24\times 6}=\frac{120}{24}=5$，与我们在开头提到的$1,2,3$有$5$种出栈序列相符。

出栈序列的个数问题与很多问题等价。例如，求$n$个左括号和$n$个右括号能组成多少合法的括号序列。这里的合法指的是每个括号都有配对。$n=3$时有$5$种：$((())),(()()),(())(),()()(),()(())$，恰与$3$个元素的出栈序列个数相同。这种括号序列问题的答案也是卡特兰数。

最后附上求任一入栈序列的所有出栈序列的代码：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int n, ans;
string s, a;
vector<char> stk;

void dfs(int i)
{
    // --- pop
    if(!stk.empty())
    {
        a.push_back(stk.back());
        if(a.size() == n)
            cout << a << '\n', ++ans;
        stk.pop_back();
        dfs(i);
        stk.push_back(a.back());
        a.pop_back();
    }
    // --- push
    if(i < n)
    {
        stk.push_back(s[i]);
        dfs(i + 1);
        stk.pop_back();
    }
}

int main()
{
    cout << "Please enter the in-stack "
        "sequence:\n>>> ";
    // e.g. ABCED
    cin >> s;
    n = s.size();
    dfs(0);
    cout << "Totally " << ans << " sequences.\n";
    return 0;
}

例如

Please enter the in-stack sequence:
>>> ABCD
ABCD
ABDC
ACBD
ACDB
ADCB
BACD
BADC
BCAD
BCDA
BDCA
CBAD
CBDA
CDBA
DCBA
Totally 14 sequences.