応用情報技術者 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