堆棧進出

有n不同的元素，堆棧進出

已經知道每個元素在推送的順序排列。

如何組合的許多不同種類能有對空間PoPing訂單？

編輯

其實我知道有2N！/（N + 1）N！^ 2點的組合，但是爲什麼呢？

2009-11-29 Mask

聽起來像一個功課問題;也許你可以告訴我們你對這個問題的思考以及你卡在哪裏？ – Amber 2009-11-29 07:57:38

作爲@AttishOculus指出的答案之一..（1）指出（+1） – 2009-11-29 08:01:02

他只是問另一個問題，這似乎是來自同一個任務（如果這確實是作業）：http://stackoverflow.com/questions/1814956 /什麼樣的遞歸，可以解決，沒有堆棧 – 2009-11-29 08:01:07

堆棧只能按一個順序彈出 - 這與元素被推送的順序相反。

2009-11-29 07:58:34 AttishOculus

是的，但OP沒有指定所有的推動發生在任何彈出之前（反之亦然）。 – Amber 2009-11-29 08:00:07

@Dav我不明白推擠和流行的交錯如何影響流行的順序，如果它真的是一個堆棧，那麼這些項目按它們推送的順序彈出，故事結束。所以我們可以選擇推動順序並改變它，但這不是很有趣，這只是簡單的組合。 – djna 2009-11-29 09:32:36

這個問題的主人太不好，不足以正確地描述問題，這樣我們就不用猜測xe的含義了...... – AttishOculus 2009-11-29 15:45:10

假設您的元素被稱爲A，B，C ......並按此順序推送。

令P（X）的平均「推X」和O（X）的平均「流行X」

設N是元件的數量。

那麼流行訂單是什麼？

當N = 1時的可能性：P（A）O（A）。（即「A」）

當N = 2時的可能性：P（A）P（B）O（B）O（A）。（「BA」）P（A）O（A）P（B）O（B）。（「AB」）

當N = 3時的可能性：ABC和BAC（從上面開始，然後是P（C）O（C）。）CBA。（來自P（A）P（B）P（C）O（C）O（B）O（A）。）但是不是 CAB，因爲如果「C」首先出現，它肯定是最後一次，所以沒有其他東西出來了，所以他們只能按照BA的順序出現。

從這種模式構建，你應該能夠構建和解決一個遞歸關係，給出你需要的答案。

2009-11-29 16:52:48 Eric

不錯的一個埃裏克。但是，當我嘗試ABC時，我有4種可能性，ABC，BAC，BCA和CBA。

可惜提出的公式不明確，因爲我不能讓n = 3從上面寫的內容的簡單解釋給出4的答案。

歸納似乎是證明公式的答案（因爲當問題的形式經常是「證明......是由公式給出......」的時候）。

而且在上述四種可能性中存在一定的對稱性，這使我認爲提出答案可能不會太困難。

編輯：其實，我們不能得到ACB嗎？ AaBCcb。大寫字母是推送，小寫字母是流行。所以，5種可能性，CAB絕對不可能。

2009-12-03 08:55:29

回答