卡兰特数(n个元素依次进栈，能得到几种不同的出栈序列)

---

情况1：如果每次入栈之前只能出栈一次：

核心代码：

// v作为栈存放数据，res作为缓存，存放出栈的元素，打印的时候res从0到n，v从n到0
void DFS(vector<char>v,vector<char>res,int circle){
  if(circle==length){
    printres(res);
    cout<<"*";
    printstack(v);
    cout<<endl;
    return;
  }
  // 不把该输入pop
  v.push_back(input[circle]);
  DFS(v,res,circle+1);
  // pop该输入
  v.pop_back();
  res.push_back(input[circle]);
  DFS(v,res,circle+1);
}

完整版的代码:

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int length=0;
vector<char>input;
void printres(vector<char>v){
  int i;
  for(i=0;i<v.size();i++){
    cout<<v[i]<<" ";
  }
}
void printstack(vector<char>v){
  while(!v.empty()){
    cout<<v.back()<<" ";
    v.pop_back();
  }
  cout<<endl;
}
void DFS(vector<char>v,vector<char>res,int circle){
  if(circle==length){
    printres(res);
    cout<<"*";
    printstack(v);
    cout<<endl;
    return;
  }
  // 不把该输入pop
  v.push_back(input[circle]);
  DFS(v,res,circle+1);
  // pop该输入
  v.pop_back();
  res.push_back(input[circle]);
  DFS(v,res,circle+1);
}
int main() {
    // freopen("test.txt","r+",stdin);
    vector<char>v;
    int i;
    scanf("%d",&length);
    char c;
    for(i=0;i<length;i++){
      cin>>c;
      input.push_back(c);
    }
    vector<char>res;
    DFS(v,res,0);
    return 0;
}
/*
3
a b c
*/

---

情况2：如果出栈次数不受限

如何计算有多少种组合？

1. 因为最后栈为空，所以0（出栈）与1（入栈）的个数应该相同。
2. 在该0-1串中若出现0大于1的情况，则必有一点满足该点及之前点中0的和==1的和-1
   image.png
3. 若将该点之后的0变成1,1变成0，则有m+n个1，m+n+2个0，所以如果总个数为2N，出现溢出的可能就有C(N+1,2N)种。
4. 所以答案就是N个元素有C(N,2N)-C(N+1,2N)种组合。

如果N个元素可以打乱进栈顺序的话，会有N!*(C(N,2N)-C(N+1,2N))

如何编码实现？

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int length=0;
void print(vector<char>v){
  int i;
  for(i=0;i<v.size();i++){
    cout<<v[i]<<" ";
  }
}
// queue用来存放键盘输入，res用来存放pop时打印的输出序列，v用来作为栈使用(最后一次性打印)
void DFS(vector<char>v,vector<char>res,queue<char>q){
  if(q.empty()){
    // 当 q.empty()时打印res然后再打印v
    print(res);
    // 输出栈中元素
    reverse(v.begin(),v.end());
    // 栈要逆向输出
    print(v);
    cout<<endl;
    return;
  }
  // pop栈v中元素然后放入res中，不需要消耗q
  if(!v.empty()){
    res.push_back(v.back());
    v.pop_back();
    // 继续递归
    DFS(v,res,q);
    // 恢复v和res的初始状态
    v.push_back(res.back());
    res.pop_back();
  }
  // 不把该输入pop,存放入栈中
  if(!q.empty()){
    v.push_back(q.front());
    q.pop();
    DFS(v,res,q);
  }
}
int main() {
    freopen("test.txt","r+",stdin);
    vector<char>res;
    queue<char>q;
    vector<char>v;
    int i;
    scanf("%d",&length);
    char c;
    for(i=0;i<length;i++){
      cin>>c;
      q.push(c);
    }
    DFS(v,res,q);
    return 0;
}
/*
3
a b c
*/

---

拓展阅读：

卡特兰数的问题应用：

• 圆周上有标号为1，2，3，4，……，2n的共计2n个点，这2n个点配对可连成n条弦，且这些弦两两不相交的方式数为卡特兰数。

  
  image.png

• 游乐园门票1元一张，每人限购一张。现在有10个小朋友排队购票，其中5个小朋友每人只有1元的钞票一张，另5个小朋友每人只有2元的钞票一张，售票员没有准备零钱。问：有多少种排队方法，使售票员总能找的开零钱？

• 甲乙两人比赛乒乓球，最后结果为20∶20，问比赛过程中甲始终领先乙的计分情形的种数。即甲在得到1分到19分的过程中始终领先乙，其种数是卡特兰数。

• Cn=n*n的方格地图中，从一个角到另外一个角，不跨越对角线的路径数，例如， 4×4方格地图中的路径有：

  
  image.png