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

此题本质上与合法出栈序列是一样的，合法解的数目为catalan数：f(n) = C(2n, n) / (n+1)。

如果进一步，求出所有合法的序列，可以参照TAOCP上的结论：若出栈序列合法，则一定不存在   1<=i<j<k<=n，使s[j]<s[k]<s[i]  ：

void GetAllValidSeqs(int *pSeq, const int k, const int n)
{
	if (k == n)
	{
		for (int i=0; i<k; i++)
		{
			cout<<pSeq[i]<<' ';
		}
		
		for (int i=0; i<n-2; ++i)
		{
			for (int j=i+1; j<n-1; ++j)
			{
				if (pSeq[i] > pSeq[j])
				{
					for (int k=j+1; k<n; ++k)
					{
						if(pSeq[k]>pSeq[j] && pSeq[k]<pSeq[i])   
							goto L1;
					}
				}
				
			}
		}
		cout<<" is valid."<<endl;
		return;

L1:		cout<<" is invalid."<<endl;
		return;

	} 
	else
	{
		for (int i=k; i<n; ++i)
		{
			mySwap(pSeq, k, i);
			GetAllValidSeqs(pSeq, k+1, n);
			mySwap(pSeq, k, i);
		}
	}
}