两个同构问题的非穷举解法

    最近，翻回了一下数据结构的书，大三上的课，现在有些内容忘了。书的最后一章“数据结构的综合应用”里面有一道N列火车进出站的问题，把问题简化了，就是N个数进出栈的问题：即N个数有多少种不同的进出栈顺序（只考虑进栈和出栈的次序，不考虑数的大小，即N个“相同”的数）。

    那时候，我是用穷举法来做的，即求出N个数的进出栈的全排列，删除存在某个位置之前进栈次数小于出栈次数的排列。现在重新想了一下，想到了自己分析过的一 道身高排队的题目：12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

 

    其实，这两个问题之前存在着一种巧妙的同构关系：在身高排队问题中，我们可以先把12个高矮不同的人按身高从低到高排成一列，每次把队头的人选择放入第一排或是第二排的队尾，此时只要保证每次把人放入队尾的时候，第一排的人数不少于第二排即可，因为这样就保证了任何时候第二排的人一定第一排的高；而在N个数的进出栈问题中，假设N=12，则可以把进栈在整个操作中的次序（整个操作由进栈和出栈组成）放到身高排队问题中的第一排，相应地把出栈的次序放到第二排，保证任何时候第一排中的进栈次数不少第二排的出栈次数即可。

 

    我修改了一下解决身高排队问题的代码，同样用非穷举的方法来解决这个问题：

import java.util.Stack;

public class PushPopStack {

	private int count = 0;
	private int total = 0;
	private Stack<Integer> pushOrders = new Stack<Integer>();	//存放进栈的次序

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

	private void printOrders() {
		for (int operOrder = 1, i = 0; operOrder <= total; operOrder++) {
			if (i < pushOrders.size() && pushOrders.get(i) == operOrder) {
				System.out.print("进  ");
				i++;
			} else {
				System.out.print("出  ");
			}
		}
		System.out.println();
	}

	private void pushOrder(int order, int level) {
		pushOrders.push(order);
		if (level >= total / 2) {
			count++;
			printOrders(); // 打印一种进出栈顺序
			pushOrders.pop();
			return;
		}

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

	public void pushPopOrder() {
		pushOrder(1, 1);
		System.out.println(total + " 个元素一共有 " + count + " 种不同的进出栈顺序。");
	}

	public static void main(String[] args) {
		PushPopStack stack = new PushPopStack(12);
		stack.pushPopOrder();
	}
}

 

    在我的博客中有篇“关于 阿里巴巴 身高排队问题的思考”的文章，里面有详细的分析解决过程 。其实，对于这两个问题还有一个便捷的求解方法，使用卡特兰公式 C(2n,n)/(n+1)，把n=N/2代入即可求得总的排列数，但这样并不能求得具体的排列次序。我在网上搜索了一下，这类同构的问题还有不少，不过在求具体的排列次序的时候很少看到非穷举的解决方法，顺便向大家问一下还有没有其它非穷举的解法。