Welcome to Rooeye's blog

卡特兰数之究极挑战

OJ rooeye 679℃ 0评论

问题:

12个高矮不同的人,排成两排,每排6个人,每一排都从矮到高排列,且第二排都比对应的第一排的人要高,问共有多少种不同的排列方式?,如果一共有n(n为偶数)个人,一共有多少种排列方式?

解释:

这道题是一道隐藏很深的卡特兰数问题

排列的形式如图所示,每排身高递增,同时第二排比对应第一排要高。



首先将12个人按照身高递增排序,这个排序是唯一的。我们要做的是在这个已经排序好的序列中挑出6个放在第一排,剩余6个放在第二排,且必须满足题目所叙述条件。我们把12人中排在第一排的人设为 -1 ,将排在第二排的人设为 1,那么我们要找的的就是符合条件的-1,1序列的个数。把从左到右遇到的第一个-1放到第一排的最左面,把从左到右遇到的第二个-1放到第一排的左二位置,依此类推。同理,我们把从左到右遇到的第一个1放到第二排的最左面,把从左到右遇到的第二个1放到第二排的左二位置,依此类推。如图给出了一种符合条件的置-1,1的方式,棕色表示1,浅绿表示-1.




序列是: -1 1 -1 1 -1 1 -1 1 -1 1 -1 1

或者这样



序列是:-1 -1 -1 -1 -1 -1 1 1 1 1 1 1

我们要做的就是如何找出合适的-1,1序列。

仔细思考就会发现:

如果 设序列为: a1 a2 ….. a12, 那么 只有对于任意k (k<=12) 满足a1+a2+…+ak <=0 的序列才是合法的,如果出现a1+a2+…+ak > 0 序列,一定不是合法的,这种情况如下图:




这种情况序列是:

-1 1 1 -1 -1 -1 1 -1 -1 1 1 1,当k = 3的时候,a1+a2+a3>0,这种情况就是违法的,原因示图如下:




在这种情况下就会出现第二排比第一排要低的情况,所以就是违法的。

同样的情况,从左到右的-1,1序列中的1的个数任何时候都不能比-1 的个数多,否则就是违法的。所以这道题就转化成如下问题:  6组(-1,1)对 进行排列,并且 从左到右遍历,1的个数不能比-1多,这就是一个典型的卡特兰数问题。
-1 1 序列的总个数是:a =  c(2n,n) ,这道题中 n = 6
-1 1 序列中违法的序列总个数是:b =  c(2n,n+1) 
符合条件的序列数就是: c = a – b = c(2n,n) /(n+1) ,结果 c 就是卡特兰数的通式

对于 a 和 b 的解释:
a =  c(2n,n) :  
有12个数字,6个-1,6个1,我们只要在12个空格中随机挑选6个放1,剩下的就自然放-1,所以就是c(12,6)。
b =  c(2n,n+1) :
对于任何一个违法序列,比如:
-1 1 1 -1 -1 -1 1 -1 -1 1 1 1 , 从第三位开始1的个数比-1多,将前三位全部取反,其余不变:

 1 -1 -1 -1 -1 -1 1 -1 -1 1 1 1


那么 -1 的个数就变成了 7,1的个数就变为了 5,仔细思考可以发现对于任何违法序列在进行如上操作后,-1的个数都会变为n+1,而1的个数都会变为n-1,实际上任何一个由 n+1 个-1,n-1个1构成的序列再进行逆反转形成后的 n个-1,n个1的序列都是违法序列,n+1个-1,n-1个1总共可以构成 c(2n,n+1)个序列,他们逆反转后全部是违法序列,互相的关系之间是一一对应的。


综上,总共的合法排序数目就是:
c(2n,n) /(n+1)

代码求解:

  1. public static int countWays(int n) {
  2. n >>= 1;
  3. int res = 1;
  4. for (int i = 2 * n; i > n; i--) {
  5. res *= i;
  6. }
  7. for (int i = 1; i <= n + 1; i++) {
  8. res /= i;
  9. }
  10. return res;
  11. }









来自为知笔记(Wiz)

转载请注明:寻梦人博客 » 卡特兰数之究极挑战

喜欢 (3)
发表我的评论
取消评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(1)个小伙伴在吐槽
  1. 嗯,是的,还有出入栈顺序,买票问题,道理都是一样的
    rooeye2015-11-24 12:36 回复