応用情報技術者 2016年 春期 午前2 問05

スタック出力順列【午前2解説】

正解の理由

解法ステップ

1. スタックの性質を確認（LIFO：後入れ先出し）。
2. 入力A, B, Cを順に処理し、各要素は一度pushされ一度popされるという制約を守る。
3. 実際に可能な出力列を、push/popの操作列として全探索または論理的に列挙する。
   • 例：Aをpushしてすぐpopすれば先頭はA（→ ABC, ACBの候補）。
   • Bを先に出す場合はAをpushしたままBをpush → Bをpop（→ BAC, BCAの候補）。
   • すべてをpushしてから順にpopすればCBA。
4. 個数を数えると5通りになる。一般化すると、長さnのときスタック出力順列の個数はカタラン数 $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$。

選択肢別の誤答解説

• ア: 3
  • 誤り。明らかにABC、ACB、BACの少なくとも3通りは可能だが、それ以外にBCAとCBAが追加で可能であるため3は不足。
• イ: 4
  • 誤り。4と考える受験者は「CABが不可能なので6-1 = 5のところをもう一つ見落としている」場合が多い。実際はもう一通り（例えばBCA）を数え漏らしている。
• ウ: 5
  • 正答。上で挙げたABC、ACB、BAC、BCA、CBAの5通りがすべて実現可能であり、他の順序（特にCAB）は不可能であるためこれが正しい。
• エ: 6
  • 誤り。全順列6通り（ABC, ACB, BAC, BCA, CAB, CBA）のうちCABがスタック制約で実現できないため最大でも5。

• ABC: +A −A +B −B +C −C
• ACB: +A −A +B +C −C −B
• BAC: +A +B −B −A +C −C
• BCA: +A +B −B +C −C −A
• CBA: +A +B +C −C −B −A

よくある誤解

1. 全順列が可能だと思う（6通り）：キューと混同していたり、スタックのLIFO制約を忘れて起こる誤りです。スタックでは入れた順序の逆順でしか取り出せない側面があります。
2. CABは可能だと誤認する：Cを先に出した後にAをBより先に出せないというスタック構造を見落とすミスです。CをpopするとBがAの上にあるためAを先にpopできません。
3. カタラン数を知らずに個別列挙を怠る：nが大きくなると手で列挙できないため、カタラン数などの一般公式を知らないと誤答につながります。

補足コラム

• 一般化：長さnの入力列に対してスタックで可能な出力列の個数はカタラン数 $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ です。今回のn=3では $C_3=5$ になります。
• 判定法：ある順列がスタックで生成可能かを判定するには「スタックシミュレーション」を行えば確実です。別の数学的特徴として、スタック生成可能な順列は「231を含まない」パターン（231-回避）として特徴付けられます。

def stack_perms(seq):
    res = []
    def dfs(inp, stack, out):
        if not inp and not stack:
            res.append(tuple(out))
            return
        # push if input available
        if inp:
            dfs(inp[1:], stack + [inp[0]], out)
        # pop if stack not empty
        if stack:
            dfs(inp, stack[:-1], out + [stack[-1]])
    dfs(list(seq), [], [])
    return res

print(stack_perms("ABC"))  # => [('A','B','C'), ('A','C','B'), ('B','A','C'), ('B','C','A'), ('C','B','A')]

FAQ