Catalan Number and parentheses

Question:

print all valid (properly opened and closed combinations of n-pairs of parentheses, and how many they would be?

for example, when n=2, there are 2 kinds:

(()) , ()()

when n=3, there are 5 kinds:

((())), (()()),(())(),()(()),()()()

Anwser:

如果直接按照题意写,可得到如下代码:

static void print_parentheses(std::string s,int ln,int rn){
  if(!ln && !rn){
    std::cout<<s<<std::endl;
    return ;
  }
  if(ln>0) print_parentheses(s+"(",ln-1,rn);  
  if(rn>ln) print_parentheses(s+")",ln,rn-1);  
}

int n=4;
std::string s;
print_parentheses(s,n,n);

但是,为了减少string的copy次数,可以改成传引用。

static void print_parentheses(std::string& s,int ln,int rn){
  if(!ln && !rn){
    std::cout<<s<<std::endl;
    s.resize(s.size()-1);
    return ;
  }
  if(ln>0) print_parentheses(s.append(1,'('),ln-1,rn);
  if(rn>ln) print_parentheses(s.append(1,')'),ln,rn-1);
  if(!s.empty()) s.resize(s.size()-1);
}

但是,到底会输出多少结果呢? 分析的过程比较麻烦。

下面我的分析不好,请参见算法导论第三版的思考题12-4。

先考虑一个简单的问题,由n个1和n个-1,组成长度为2n的序列,有多少种可能性?

答:C(2n, n)种。我们从2n的位置上挑选n个,把1放进去,共有C(2n,n)种可能性。剩下的位置恰好放-1。

然后我们来考虑下,不平衡的情况有多少种。如果对某个序列,能找到正整数k,使得它的前k项和为负数,那么就说这个序列是不平衡的。

对于一个不平衡的序列,假如它的前k项和等于-1(1<=k<2n),然后它后面的2n-k项的和一定是1。因为总体全部加起来,和应该是0 。

此时,我们把后面2n-k项进行一次翻转,就是,1变成-1,-1变成1。那么整个序列就有n+1个-1,和n-1个1。

如果我们用n-1个1和n+1个-1,组成长度为2n的序列,有多少种可能性? 答:C(2n, n+1)种。(或者C(2n, n-1)种也对)

由于这个序列的所有项的和是-2,所以一定能找到一个整数k(1<=k<2n),使得前k项的和为-1。通过翻转后面的项,每个这样的序列都对应着一个前面所说的不平衡的序列。

所以,回到最初的问题,所有properly opened and closed combinations 有多少?

答: C(2n,n) - C(2n,n+1) = C(2n,n) - (n/n+1)C(2n,n) = C(2n,n)/(n+1)。

由于这个数字增长很快,所以实际情况中n一定不会很大。所以用递归来解它是很合适的,栈不会爆掉。

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥