如何准确的计算输出的排列的数目，以及如何生成排列，是需要考虑的问题。
当前共有两个问题：计数和生成排列。
先给出关于问题的具体的描述：假设有一输入序列为1到n升序，求堆栈可能的输出。
验证合法的法则:
首先寻找合法输出的形式。
假设输出序列是p1到pn。
则若pi已知，求pi＋1可能的数是？
首先考虑一个实例：
123
输出可能是 123 132 213 231 321
若pi＋1大于pi，则是可以的，因为pi在pi＋1之后进入堆栈；
若pi+1小于pi，则pi＋1一定是所有小于pi的数中没有出栈的最大的数 集合描述是｛1 ... pi｝ - {pm| m < i};
接着考虑是否有合适的递推关系:
假设an 是所有n的输出排列的集合, 则从an中去掉n之后的集合属于an-1;
可以通过以上的验证合法法则进行证明;
所以根据此可以得知: an能够通过an-1以某种形式构造出来.
考虑实际例子:
1
12 21
123 132 213 231 321
1234 1243 1324 1342 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321
以上可知: 对于n可以放在an-1的某个排列的末尾;
如果n放在某个排列的中间, 则要求n之后的排列必须是降序的;
(可以根据合法性法则证明).
观察一下每次添加n时的规律:
每个排列最多有n中添加, 最少有两种添加;
排列 添加形式 添加的个数
对于1 有 12 21 2
对于 12 有 123 132 2
对于21 有 213 231 321 3
对于123 1234 1243 2
132 1324 1342 1432 3
213 2134 2143 2
231 2314 2341 2431 3
321 3214 3241 3421 4321 4
a1 = 1 a2 = 2 a3 = 5 a4 = 14
所以 an = an-1 + 3^(n-2)
所以 an = 1 + (3^(n-1) -1) /2;
作者：liyonghelpme 发表于2010/7/7 13:34:00 原文链接
阅读：522 评论：0 查看评论