C# 經典題：單口管子放球 (棧模型) 產生所有合法出棧序列

題目：4 顆球 a,b,c,d 依序放入單口管子 (棧)，求所有可能的取出順序。這是經典的**棧排列 / Catalan 數**問題，n=4 時有 C₄=14 種合法序列。

數學模型

• 操作序列：+ 代表推入 (push)，- 代表彈出 (pop)
• 合法序列條件：任意前綴中 + 數量 ≥ - 數量，總數各 4 個
• 對應 Catalan 數：Cₙ = (2n)! / ((n+1)! n!) → C₄ = 14

遞迴生成所有合法操作序列

using System;
using System.Collections.Generic;

class Program {
    static IEnumerable GenerateOps(string current, int pushCount, int popCount, int n) {
        if (pushCount == n && popCount == n) {
            yield return current;
            yield break;
        }
        // 可推入
        if (pushCount < n) {
            foreach (var s in GenerateOps(current + "+", pushCount + 1, popCount, n))
                yield return s;
        }
        // 可彈出 (棧不為空)
        if (popCount < pushCount) {
            foreach (var s in GenerateOps(current + "-", pushCount, popCount + 1, n))
                yield return s;
        }
    }

    static void DisplaySequence(string ops) {
        Console.Write(ops + "\t");
        var stack = new Stack();
        char nextBall = 'a';
        foreach (char op in ops) {
            if (op == '+') stack.Push(nextBall++);
            else Console.Write(stack.Pop());
        }
        Console.WriteLine();
    }

    static void Main() {
        foreach (var ops in GenerateOps("", 0, 0, 4))
            DisplaySequence(ops);
    }
}

輸出結果 (14 種)

+-+-+-+-    abcd
+-+-++--    abdc
+-++--+-    acbd
+-++-+--    acdb
+-+++---    adcb
++--+-+-    bacd
++--++--    badc
++-+--+-    bcad
++-+-+--    bcda
++-++---    bdca
+++---+-    cbad
+++--+--    cbda
+++-+---    cdba
++++----    dcba

核心邏輯解析

1. GenerateOps 遞迴構建操作字串，pushCount 追蹤已推入球數，popCount 追蹤已彈出球數。
2. 剪枝條件：popCount < pushCount 確保棧不為空才能彈出。
3. DisplaySequence 模擬棧操作：+ 推入下一顆球 (nextBall++)，- 彈出並輸出。

擴展：任意 n 的通用解

static IEnumerable GetStackPermutations(int n) {
    return GenerateOps("", 0, 0, n);
}
// n=5 → 42 種, n=6 → 132 種...

此題完美展示「遞迴生成 + 模擬驗證」解決組合學問題的標準思路，也是面試高頻考點。