关于 阿里巴巴 身高排队问题的思考

首先来重复一下问题（具体可以浏览thinke365的帖子http://www.iteye.com/topic/503191 ）

12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

 

我们可以从如下几个方面来分析这个问题：

 

a. 先把这12个高矮不同的人按身高递增的顺序排成1列，并依次从1到12编号来简化不同身高的表示方法；

 

b. 如果第一排的排列次序已确定的话，那么第二排的排列就自然确定；

 

c. 显然，如果只有编号为1和2的2个人的话，排列方式只有一种（1）（2）；

 

d. 对于编号为1 - n的每一种符合条件的排列（n为偶数，并且假设第一排末尾的编号为x），在第一排加入n+1和在第二排加入n+2可以产生一种符合条件的编号为1 - (n+2)的排列；

 

e. 在d条件下，可以把新加入第一排的n+1替换成 大于x且小于n+1 的编号（即第一排新末尾的编号值x'的取值范围为大于x且小于等于n+1），因为这样的替换保证了新的第一排的排列都是从原来的第一排生成的（即第一排的前n/2个排列与原来的相同），而且在第二排中加入编号n+1后会使第二排的某个编号值变大（因为第二排中的n+2不会被换出）。显然，无论第二排中哪个编号变大，只要重新按编号递增排列第二排， 都会保证原来 的 第二排比对应的第一排的人高（即编号较大），而第二排末尾的编号n+2总是能够确保大于第一排的末位；

 

因此，我们可以根据以上分析来画出从 编号为1 - n的排列 到 编号为1 - (n+2)的排列 的状态转换树（n=2,4,6的情况）：

以上状态转换树只画出了第一排的状态转换，对于第3层，它的n+1=5，n+2=6，显然n+2的值即为节点层序值的2倍

 

所以，求编号为1 - 12的排列总数，就是求该树的第6层的节点数，而从根节点1到第6层的每个节点的路径就是一个符合条件的第一排排列（可以用树的遍历算法求得）。 对于每个节点我们可以赋它的编号值为order和层序值为level，以下是简单计算第6层节点数的方法：

private void firstOrder(int order, int level) {
	place.add(order);
	if (level >= 6) {
		count++;
		place.pop();
		return;
	}

	for (int i = order + 1; i < 2 * (level + 1); i++)
		firstOrder(i, level + 1);
	place.pop();
}

以下是计算并打印第一排排列的完整代码：

import java.util.Stack;

public class TwoOrderQueue {

	private int count = 0;
	private int total = 0;
	private Stack<Integer> place = new Stack<Integer>();

	public TwoOrderQueue(int total) {
		this.total = total;
	}

	private void firstOrder(int order, int level) {
		place.add(order);
		if (level >= total / 2) {
			//计数叶结点并打印路径
			count++;
			for (Integer i : place)
				System.out.print(i + " ");
			System.out.println();
			place.pop();
			return;
		}

		//展开编号为order的节点的子树，并进入下一层 level+1
		for (int i = order + 1; i < 2 * (level + 1); i++)
			firstOrder(i, level + 1);
		place.pop();
	}

	public void firstOrder() {
		firstOrder(1, 1);
		System.out.println("第一排一共有" + count + "种排列");
	}

	public static void main(String[] args) {
		TwoOrderQueue q = new TwoOrderQueue(12);
		q.firstOrder();
	}
}

 

小结：

我们把12个高矮不同的人按身高递增的顺序排成1列，并依次从1到12编号，这里面除了简化问题之外，还存在什么样的思维切入点呢？我们把12个人分为2列，这里隐含了一个“有序”的方法，即假设有2个空队列，12个人依次选择是进入第1个队列还是第2个队列，最后只要两队人数相同即可。显然，这12个人进入队列的次序是可以任意的，那么我们为什么不选择一种有序的次序呢？而最明显的一种有序的次序就属身高递增的次序了，把他们依次编号的话不仅可以区分不同的身高，还表示了依次进入队列的次序，这样就最容易在加入队列的过程中找出规律。

我们都知道，计算机最擅长的就是使用规则来求解规范的问题 。比如单纯形法，第一步就是要把线性方程组规范化，而这里问题最好的规范化就是问题分析中的a步骤。

 

使用排列组合的方法求解（参见thinke365帖子中BenArfa的解答）：

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