Catalan Number: 身高排队算法

身高排队算法-(较优解):12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种? - nicebooks的专栏 - 博客频道 - CSDN.NET
12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

这个公式是F(n) = (n! / ((n/2)! * (n/2)!))/ (n/2 +1)）.

下面数值表示的是位置，

0   1   2   3   4   5

6   7   8   9 10 11

对于位置0，可能的数的范围是0
对于位置1，可能的数的范围是1，2
对于位置2，可能的数的范围是2，3，4
对于位置3，可能的数的范围是3，4，5，6
对于位置4，可能的数的范围是4，5，6，7，8
对于位置5，可能的数的范围是5，6，7，8，9，10
对于位置为n的数，其数的范围是[n, 2n].

只要从12个人中挑选6个人放在第一排，那么所有的人的位置就都确定了，因为是要求按身高排序的。
这里我们的挑选方法以及限制条件是这样的：12个人先从矮到高排序，然后每个人被选到第一排或者第二排，如果要满足题意，当且仅当每挑选完一次之后，第二排中的人数不多于第一排中的人数，而这个条件的排列就是 C(12,6) - C(12,5) = 132

http://zhangjinkun.com/2015/11/24/5fa521ba1a422e92c24ca6ab88f5c8ae/

同样的情况，从左到右的-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. }

Recursive Solution
http://blog.csdn.net/wuzhekai1985/article/details/6713094
假设已按高矮顺序编号从0到11，即0号最矮、11号最高，(i, j)表示某个人在队列中的位置。对于0号只能排在(0, 0)，1号可以排在两个位置(0, 1)和(1, 0)。2号可以排的位置取决于1号的位置，如果1号排在(0, 1)，那么2号可以排在两个位置(0, 0)和(1, 0)。如果1号排在(1, 0)，那么2号只能排在(0, 1)。
观察一下，可以得出一下规律：对于i号，如果第一排与第二排的人数一样，那么他只能排在第一排；如果第一排的人数大于第二排，那么他可以排在第一排或者第二排。递归终止的条件是第一排或第二排排满了

void InLineProblem(int firstFree, int secondFree, int num)
{
 if(firstFree == num/2 || secondFree == num/2) //其中一排无剩余位置
 {
  totalNum++;
  return;
 }
 if(firstFree == secondFree) //第1排人数与第2排人数一样
 {
  InLineProblem(firstFree + 1, secondFree, num); //只能排在第1排
 }
 else
 {
  InLineProblem(firstFree + 1, secondFree, num); //排在第1排
  InLineProblem(firstFree, secondFree + 1, num); //排在第2排
 }
}

http://blog.csdn.net/u011824857/article/details/38794153

分析：这是一个子集树问题，这里的子集指的是站在前排人的集合。

            约束条件：front < 6 && front >= back

            限界条件：back < 6 && front >back

1.     // 不变信息  
2.     static int n;  
3.     // 动态改变信息  
4.     static int front;// 记录前排的数目  
5.     static int back;// 记录后排的数目  
6.     static int count;// 记录解数目  
7.   
8.     /** 
9.      * @author zhangmeng 
10.      *@param i 表示第i层，此时决定第i+1个人的位置 
11.      */  
12.     private static void trackback(int i) {   
13.         // 更新front  
14.         if (i < n) {  
15.             // 如果满足约束条件，搜索左子树  
16.             if (front < 6 && front >= back) {  
17.                 // 搜索左子树  
18.                 front++;  
19.                 LineUp.trackback(i + 1);  
20.                 //清理现场  
21.                 front--;  
22.             }  
23.             // 如果 满足上界函数，搜索右子树  
24.             if (back < 6 && front >back) {  
25.                 // 更新cx  
26.                 back++;  
27.                 trackback(i + 1);  
28.                 //清理现场  
29.                 back--;  
30.             }  
31.         }else{//处理第n层  
32.             count++;  
33.             return;  
34.         }  
35.     }  
36.   
37.     public static int LineUpCount() {  
38.         LineUp.n = 12;  
39.         LineUp.back = 0;  
40.         LineUp.front = 0;  
41.         LineUp.count = 0;  
42.         trackback(0);  
43.         return LineUp.count;  
44.     }  

http://onestraw.net/cprogram/12-height-of-different-people/
http://billowkiller.com/blog/2014/08/09/Number-theory-introduction/
Read full article from 身高排队算法-(较优解):12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种? - nicebooks的专栏 - 博客频道 - CSDN.NET