排队问题

最近许多人认为我已经工作了，认为我文章应该会天天更新，我在这里再次声明我是学生，这学期课比较多，课后作业也有点多，文章只能周末放假时更新，给大家带来了不便，敬请谅解。

今天我要讲的东西是关于排队的问题，实际上这个问题是算法课的老师给我们出的问题，到时候会有测验。问题是这样的，有2n个人，排两排，从矮到高，第二排的要比第一排所对应的那个人高，问有多少种排列方式？

正常操作

我讲解的时候假设n=5，那么2n就等于10，我们把10个人分别编号（从0到9，0表示最矮的，9表示最高的），想都不用想，第一排第一个必然是0，最后一排最后一个必然是9，然后就是选出从2n-2（除去最小的和最大的）个人里面选出n-1个人放在第一排，也就是最小值的后面，然后排好序。2n-2里面还剩下n-1个人，将这n-1个人放在第二排，也就是最大值的前面，同样要排好序。然后对应着比较，在同一列，如果存在第一排的比第二排高，计数器置0（默认为1），然后累加就是总数。说了这么多，该编码实现一下了。

这个函数参数n是一排的人数，返回的count表示总共有多少种排法。函数的具体实现首先是要导入itertools模块，这里的导入和平常的导入不一样，因为平常的导入是静态的导入，程序结束才会把模块中的对象（Python一切皆对象。）销毁，而通过这个动态导入，函数fun一结束模块对象就被析构了。然后是总数的初值count = 0，接下来生成一个列表，[0, …, 2n-1]共有2n个元素，然后使用itertools模块中的combinations函数从[1, …,2n-2]当中选出n-1个，然后去迭代这个元组列表（一个列表，其中的每一个元素是一个元组），在每一次迭代生成一个row0的列表并排序，表示第一排的排列方式。接下来就是把剩余的元素放到row1的列表中并排序，这是第二排的排列方式。最后就是每一列对应比较。如果这个排列有效，也就是对于任意的k∈[1, n-1)（为什么不是0到n？因为第0行第0列是最小值0，没有比它小的数，也就是说第1行第0列任何一个数都比它大，所以没有比较的必要，同理可得最后一列也没有比较的必要），都满足这个条件row0[k] < row1[k]，计数器+1，等这个循环结束后，将总数返回出去即可。

标记

上面一种方法我讲完了，接下来是第二种方法，通过标记来表示那个人到底是放在第一排还是第二排，在这里，用0表示放在第一排，1表示放在第二排，我们需要定义一个列表存放这两个数。（讲解时还是和上面的一样，10个人为例）0000011111表示排序方式如下：

0 1 2 3 4 5 6 7 8 9

其他情况大家可以自己尝试列一下。通过观察1的出现，我们考虑这一个出现能不能放在第二排，显然，在这个1之前出现的那些0，1对应的人要么是在这个1左边，要么是在这个1前面。而肯定要有一个0的，在这个1前面，统计在这个1之前的0和1的个数。也就是要求，0的个数大于1的个数。我们可以把0看成入栈，1看成出栈，问题也就转换为n个元素合法的入栈出栈的情况有多少种？

卡特兰数

在具体实现之前，首先介绍一下卡特兰数。卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名，其前几项为（从第零项开始） : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

令h(0)=1,h(1)=1，catalan数满足递推式： h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)*h(0) (n>=2) 例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2 h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5 另类递推式： h(n)=h(n-1)*(4*n-2)/(n+1); 递推关系的解为： h(n)=C(2n,n)/(n+1) (n=0,1,2,…) 递推关系的另类解为： h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,…)

问题大意是用S表示入栈，X表示出栈，那么合法的序列有多少个(S的个数为n)显然有c(2n, n)个含S，X各n个的序列，剩下的是计算不允许的序列数(它包含正确个数的S和X，但是违背其它条件)。在任何不允许的序列中，定出使得X的个数超过S的个数的第一个X的位置。然后在导致并包括这个X的部分序列中，以S代替所有的X并以X代表所有的S。结果是一个有n+1个S和n-1个X的序列。反过来，对后一种类型的每个序列，我们都能逆转这个过程，而且找出导致它的前一种类型的不允许序列。例如XXSXSSSXXSSS必然来自SSXSXXXXXSSS。这个对应说明，不允许的序列的个数是c(2n, n-1)，因此an = c(2n, n) - c(2n, n-1)。