指定された位置に開き括弧を含むバランスの取れた式をC++で数える方法

バランスの取れた括弧式とは、あらゆる種類の括弧が正しい順序で対になっている式のことです。つまり、すべての開き括弧に対して、適切な順序で対応する閉じ括弧が存在している必要があります(例:{ })。

入力例 − {([][]{})({}[]{})}

出力 − balanced(バランスが取れている)

本記事では、与えられた数の括弧から作成できるすべてのバランスの取れた式のうち、指定された位置に必ず開き括弧が配置されるものを数える問題を扱います。

具体的には、整数 n と、長さ 2n の括弧の位置情報を表す配列が与えられます。「1」でマークされた位置には必ず開き括弧「{」が配置されるという条件のもとで、条件を満たす長さ 2n のバランスの取れた式の総数を求めます。

例 −

Input : n = 2 , position [1, 0, 0, 0]
Output : 2
Explanation : 考えられるすべての組み合わせは {{}} と {}{} の 2 通りです。

アルゴリズム

• 「1」が設定されているすべての位置は、開き括弧として固定します。

• 以下のルールに従って再帰的に処理を進めます。

  • 開き括弧と閉じ括弧の差(未対応の開き括弧の数)が負になった場合は、その時点で 0 を返します。

  • インデックスが n に達したとき、push と pop を繰り返した後の括弧の合計が 0 であれば 1 を返します(解が 1 つ得られたことを意味します)。それ以外の場合は 0 を返します。

  • 式の現在の位置に 1 が事前に割り当てられている場合は、インデックスを 1 進めて再帰的に呼び出し、開き括弧の数を増やします。

  • それ以外の場合は、現在の位置に開き括弧を挿入するケースと閉じ括弧を挿入するケースの両方について再帰的に関数を呼び出し、括弧の合計数を調整しながら次のインデックスへ進みます。

プログラム

#include <bits/stdc++.h>
using namespace std;
int find(int index, int openbrk, int n, int expression[]){
   if (openbrk < 0)
      return 0;
   if (index == n){
      if (openbrk == 0)
         return 1;
      else
         return 0;
   }
   if (expression[index] == 1) {
      return find(index + 1, openbrk + 1, n, expression);
   } else {
      return find(index + 1, openbrk + 1, n, expression) + find(index + 1, openbrk - 1, n, expression);
   }
}
int main() {
   int n = 3;
   int expression[6] = { 1, 0, 1, 0, 0, 0};
   cout << find(0, 0, 2 * n, expression) <<endl;
   return 0;
}

出力

3

コードのポイント

find 関数は、現在処理中のインデックス index と、それまでに出現した開き括弧と閉じ括弧の差 openbrk を引数として受け取ります。openbrk が負になるのは、閉じ括弧が対応する開き括弧より先に現れたことを意味するため、その経路は無効として 0 を返します。

位置が「1」で固定されている場合は開き括弧のみを選択できますが、自由な位置では開き括弧・閉じ括弧の両方を試すため、結果は 2 つの再帰呼び出しの和となります。最終的にすべての位置を処理し終えた時点で openbrk が 0 になっていれば、その式はバランスが取れていると判定され、カウントに加算されます。

この手法の時間計算量は、自由な位置ごとに分岐が発生するため指数オーダー(O(2^m)、m は自由な位置の数)となります。一方、再帰の深さは最大 2n であるため、空間計算量は O(n) です。