假如現(xiàn)在有這么一個問題:
一個序列從1到n依次入棧, 那么可能的出棧序列一共有多少種?
注意: 在任意一個時刻,只要棧不為空, 就可能有元素出棧, 不是說元素全部入棧之后再出棧
這個問題的解其實(shí)等同于求n階的卡特蘭數(shù)(catalan)
先給出問題的解
設(shè)n階的卡特蘭數(shù)為k(n), 那么
k(0) = 1, k(1) = 1
k(n) = k(0) * k(n - 1) + k(1) * k(n - 2) + ... + k(n - 2) * k(1) + k(n - 1) * k(0)
或者
k(n) = c(2n, n) / (n + 1)
或者
k(n) = c(2n, n) - c(2n, n-1)
下面是問題的具體分析過程
首先說明為什么問題的解是卡特蘭數(shù)
卡特蘭數(shù)指的是在一個n*n的方格中,從左下角走到右上角. 每一步只能往右或者往上, 且在走的過程中不能越過從左下角到右上角的那條對角線.
和入棧出棧問題對比可以發(fā)現(xiàn), 這里的往右走就相當(dāng)于入棧, 往上走就相當(dāng)于出棧, 對角線上的點(diǎn)就相當(dāng)于棧為空的時候, 不能越過對角線就是說在棧為空的時候不能執(zhí)行彈棧操作
那么卡特蘭數(shù)如何求得呢, 思路有很多,這里說幾種比較容易理解的
1. 用排列組合的方法來求
我們借助棧的思想來理解
n個元素入棧再出棧, 那么就有 2n 次操作, 正常情況下是n次入棧操作, n次出棧操作, 根據(jù)排列組合的方法, 共有 c(2n, n) 種可能性
當(dāng)然了,在這 c(2n, n) 種可能性中, 肯定是有非法操作的, 也就是在在為空或者為負(fù)的時候進(jìn)行出棧操作, 那么非法的情況一共有多少種呢?
我們假設(shè)在第一次出現(xiàn)非法操作的時候, 這個時候棧中元素個數(shù)為 -1 , 因?yàn)樵跊]有元素的時候進(jìn)行了出棧操作. 由于最終棧中元素?cái)?shù)量為 0 , 那么在這一步之后的操作中,入棧次數(shù)肯定比出棧次數(shù)多 1 . 如果我們對這次操作之后的所有操作進(jìn)行反轉(zhuǎn), 那么最終棧中元素的數(shù)量就是 -1 減去 1 = -2 了. 這就是非法的情況.
在非法的情況下, 由于最終棧中元素?cái)?shù)為-2, 所以在2n次操作中, 肯定有 n - 1 次入棧操作, n + 1 次出棧操作. 這時入棧次數(shù)和出棧次數(shù)不同是因?yàn)槲覀儗Σ糠植僮鬟M(jìn)行了反轉(zhuǎn), 這一點(diǎn)要明白.
到這里, 答案就很明顯了, 非法操作的次數(shù)為 c(2n, n -1) = c(2n, n + 1)
所以合法的次數(shù)等于所有可能的次數(shù)減去非法的次數(shù), 即:
k(n) = c(2n, n) - c(2n, n-1)
2. 折線法
這種方法其實(shí)與第一種方法有異曲同工之妙, 只是運(yùn)用了圖形來幫助理解
我們假設(shè)一個人在原點(diǎn)汉买，操作1是此人沿右上角45°走一個單位（一個單位設(shè)為根號2，這樣他第一次進(jìn)行操作1就剛好走到（1,1）點(diǎn)）佩脊，操作2是此人沿右下角45°走一個單位蛙粘。第k次操作2前必須先進(jìn)行至少k次操作1，就是說明所走出來的折線不能跨越x軸走到y(tǒng)=-1這條線上威彰！在進(jìn)行n次操作1和n此操作2后出牧，此人必將到到達(dá)（2n，0）歇盼！若無跨越x軸的限制舔痕，折線的種數(shù)將為 c（2n，n），即在 2n 次操作中選出n次作為操作1的方法數(shù)赵讯。
現(xiàn)在只要減去跨越了x軸的情況數(shù)盈咳。對于任意跨越x軸的情況，必有將與 y = -1相交边翼。找出第一個與 y = -1 相交的點(diǎn) k，將k點(diǎn)以右的折線根據(jù) y = -1 對稱（即操作1與操作2互換了）鸣剪∽榈祝可以發(fā)現(xiàn)終點(diǎn)最終都會從（2n，0）對稱到（2n筐骇，-2）债鸡。由于對稱總是能進(jìn)行的，且是可逆的铛纬。我們可以得出所有跨越了x軸的折線總數(shù)是與從（0,0）到（2n,-2）的折線總數(shù)厌均。而后者的操作2比操作1要多 0-（-2）=2次。即操作 1 為 n-1 , 操作 2 為 n+1告唆」妆祝總數(shù)為 c（2n，n-1）擒悬。
3. 遞歸的方法
若用（n模她，m）表示有n個元素還沒有入棧，棧內(nèi)目前有m個元素時懂牧，出棾蘧唬可能的種數(shù)。則問題就是（n僧凤，0）畜侦。
當(dāng)目前狀態(tài)為（n, 0)時只能進(jìn)行入棧操作，則有(n, 0) = (n - 1, 1)躯保。當(dāng)m>=1時旋膳，可以入棧也可以出棧則有(n, m) = (n - 1, m + 1) + (n, m - 1)。顯然(0, m) = 1吻氧。這樣就有了終止條件溺忧。
以上思路可以用遞歸程序?qū)崿F(xiàn)
function catalan(n)
{
return condition(n, 0)
}
/*
* 遞歸函數(shù), 用來求特定的某個時刻對應(yīng)的可能性種數(shù)
*
* @param total - 還沒有入棧的元素的個數(shù)
*
* @param inStack - 當(dāng)前棧中元素個數(shù)
*
*/
function condition(outStack, inStack)
{
if(outStack === 0)
{
return 1
}
if(inStack === 0)
{
return condition(outStack - 1, 1)
}
return condition(outStack - 1, inStack + 1) + condition(outStack, inStack - 1)
// 注意, 這里第二項(xiàng)inStack減少1然而outStack沒有加1是因?yàn)檫@個出棧的元素已經(jīng)不必再考察了, 我們
// 只需要關(guān)注后面的還沒有入棧元素即可
}
// 測試
for(let i = 1; i <= 10; i ++)
{
console.log(`${i}階卡特蘭數(shù)為: ${catalan(i)}`)
}
// 1階卡特蘭數(shù)為: 1
// 2階卡特蘭數(shù)為: 2
// 3階卡特蘭數(shù)為: 5
// 4階卡特蘭數(shù)為: 14
// 5階卡特蘭數(shù)為: 42
// 6階卡特蘭數(shù)為: 132
// 7階卡特蘭數(shù)為: 429
// 8階卡特蘭數(shù)為: 1430
// 9階卡特蘭數(shù)為: 4862
// 10階卡特蘭數(shù)為: 16796
