【ITニュース解説】Generating Stack Permutations: A Recursive Thinking Process

1からnまでの連続する数字を、決まった順序（1, 2, 3, ..., nの順番）でスタックに格納（プッシュ）しなければならないが、スタックから数字を取り出す（ポップ）タイミングは自由に選べるという問題がある。このプッシュとポップの操作を組み合わせることで、最終的にどのような数字の並び（順列）が得られるのか、可能なすべてのパターンを生成することを考える。プッシュする数字の順序は固定されているが、ポップのタイミングが柔軟である点がこの問題の鍵となる。

この問題を解決する上での核心的な考え方は、どの時点においても常に二つの選択肢が存在することである。一つは、もしスタックが空でなければ、スタックのいちばん上にある数字を取り出す（ポップする）操作。もう一つは、まだスタックに格納されていない次の数字をスタックに入れる（プッシュする）操作である。これらの選択肢が、それぞれ異なる結果への道筋となり、まるで枝分かれする木（決定木）のように、可能なすべての操作の経路を表現できる。

この決定木を効率的に探索するために、「再帰」というプログラミングのテクニックを利用する。再帰とは、ある大きな問題を解くために、その問題よりも少し小さな同じ種類の問題を解く、という考え方である。具体的には、再帰関数を定義し、その関数が現在の操作状況を表すいくつかの情報を管理する。管理する情報は主に三つで、一つ目は次にスタックにプッシュすべき数字（まだプッシュされていない最小の数字）、二つ目は現在のスタックの中身、三つ目はこれまでにスタックから取り出された（ポップされた）数字の並びである。この三つの情報があれば、あらゆる状況から次の操作を判断し、再帰的に処理を進めることができる。

例えば、n=2（数字の1と2を扱う）の場合を考えてみる。最初は、次にプッシュすべき数字は1、スタックは空、出力リストも空の状態から始まる。 一つ目のパスとして、「まずプッシュしきってからポップする」という操作をたどってみる。まず1をプッシュするとスタックは[1]となり、次にプッシュすべきは2になる。次に2をプッシュするとスタックは[1,2]となり、次にプッシュすべき数字はもうない。これでプッシュが完了したので、今度はポップを始める。スタックの最上部にある2をポップすると、出力は[2]となりスタックは[1]になる。続いてスタックの最上部にある1をポップすると、出力は[2,1]となりスタックは空になる。出力リストのサイズがn（この場合は2）と等しくなったため、一つの有効な順列[2,1]が生成されたことになる。 二つ目のパスとして、「途中でポップを挟む」という操作を考えてみる。まず1をプッシュするとスタックは[1]、次にプッシュすべきは2となる。ここでスタックが空ではないので、1をポップする選択肢を選んでみる。出力は[1]となりスタックは空になる。次にまだプッシュされていない2をプッシュするとスタックは[2]、次にプッシュすべき数字はもうない。最後にスタックの最上部にある2をポップすると、出力は[1,2]となりスタックは空になる。これも出力リストのサイズがnと等しくなったため、もう一つの有効な順列[1,2]が生成された。 このように、様々なプッシュとポップの組み合わせによって、異なる出力順列が生成される。

実際のプログラムでは、この再帰関数が深さ優先探索（DFS）と呼ばれる方法で、決定木のすべての可能な経路を探索していく。関数が呼び出されるたびに、先ほど説明した二つの選択肢を順番に試す。 まず一つ目の選択肢として、「スタックからポップする」場合を考える。もしスタックが空でなければ、スタックの最上部にある数字を取り出し（ポップ）、それを出力リストに追加する。この状態で、再び自分自身（再帰関数）を呼び出す。この再帰呼び出しから戻ってきたら、別のパス（選択肢）を試すために、先ほどポップした数字をスタックに戻し（プッシュし直す）、出力リストからもその数字を削除する。この「状態を元に戻す」操作を「バックトラッキング」と呼ぶ。これにより、他の選択肢を探索する際に、それ以前の操作の影響を受けずに、独立した状態から探索を始められる。 次に二つ目の選択肢として、「次の数字をスタックにプッシュする」場合を考える。まだプッシュすべき数字が残っている場合（例えば、1からnまでのすべての数字をプッシュしきっていない場合）、次にプッシュすべき数字をスタックに入れ、次にプッシュすべき数字を一つ進める（例えば1の次は2）。そしてこの状態で、再び自分自身（再帰関数）を呼び出す。この再帰呼び出しから戻ってきたら、同様にバックトラッキングを行う。つまり、先ほどスタックに入れた数字をスタックから取り出す（ポップする）。

再帰関数の終了条件は、出力リストのサイズがnになったとき、つまりすべての数字がスタックから取り出されて一つの順列が完成したときである。この条件を満たしたら、完成した順列を出力し、そのパスの探索は完了となる。

このスタック順列の生成問題は、計算機科学の分野でいくつかの興味深い概念と関連があることが知られている。例えば、n個の数字から生成される可能なスタック順列の総数は、「カタラン数」という特別な数列によって与えられる。また、プッシュ操作を左括弧「(」、ポップ操作を右括弧「)」と見なすと、有効なスタック順列は、数学的に「バランスの取れた括弧の並び」に対応することもできる。これは、括弧の開閉が正しく対応していることを意味し、プログラミング言語の構文解析などにも関連する考え方である。さらに、この問題は、二分木を探索してすべての可能な経路を生成するプロセスとも考え方が似ている。

このように、一見すると複雑な組み合わせの問題でも、「どの段階でどのような選択肢があるか」を明確にし、「その選択肢を一つずつ再帰的に試していく」という思考プロセスを用いることで、体系的にすべての可能性を見つけ出すことができる。再帰とバックトラッキングは、このような意思決定の木を効率的に探索し、複雑な問題を解決するための強力なプログラミングツールである。