Clever Geek Handbook

ランダムな括弧シーケンスを生成する方法

こんにちは、Habr！



アルゴリズムをテストするとき、私はしばしばランダムなバイナリツリーを生成するタスクを持っています。 さらに、ウィッシュリストはランダムなツリーではなく、均一な分布から取得されます。 見かけの単純さにもかかわらず、このようなツリーを効果的に構築することは完全に重要です。



この記事のタイトルには「ブラケットシーケンス」という単語が含まれています。 これらの単語の背後には、ブラケットの助けを借りて、バイナリツリーを含む非常に多様なオブジェクトを記述することができるため、さらに何かが隠されています。 Habréでは、この事実について別の投稿が行われました。



この記事では、線形時間を含むランダムブラケットシーケンスを生成するいくつかの方法を説明し、シーケンスをバイナリツリーに変換する例を示します。 面白い？





挑戦する



nを指定すると、長さ2 nのすべての正しいシーケンスの一様分布に従って、正しいブラケットシーケンスを生成します。



在庫



長さ2 nの通常のブラケットシーケンスの数は、カタロニア語のn番目の数に等しいことが知られています。 。 カタロニア語の数を計算するには、明示的な



そして再帰的



数式。



乱数ジェネレーターが必要です。 nが与えられると、0から同じ確率の乱数を生成します。 。 また、リストに対するランダム順列ジェネレーターが役立ちます。 Pythonでは、random.shuffleと呼ばれます。 線形時間で動作し、シーケンス1,2、...、 nの一様分布に従ってランダムな順列を生成すれば十分です。



Avosと言う3つの方法



動的プログラミングの力



すべての正しいブラケットシーケンスに番号を付けることができるという考えがあります。 また、たとえば、これを行う方法の詳細な説明があります。 そのため、このような計画を実装できます。



計画はほぼ優れています。 つまり nが30未満の場合、計画は非常に良好です。しかし、nが1千のオーダーであることが判明した場合、長い計算が必要になります。 そのような計画に遅れずについていくために、私はたくさん汗をかかなければならないと思う 。 別の方法を探しましょう。



試してみてください



カタロニア語の数値の明示的な式をもう一度見てみましょう。

。

実際には、多くの正しいブラケットシーケンスがあることを意味します。



開いたり閉じたりする括弧の数が同じ場合、 バランスの取れたシーケンスを呼び出します。 たとえば、シーケンス")(()"



、 "()()"



はバランスが取れていますが、シーケンス"()))"



はバランスが取れていません。 明らかに、正しいシーケンスはバランスが取れています。 合計で、長さ2nのすべてのバランスの取れたシーケンスが存在します 。 これらのシーケンスのいずれかがランダムに選択された場合、それは確率で正しいでしょう



新しい計画。

  1. 一様分布に従って、ランダムバランスブラケットシーケンスを生成します。
  2. 正しいことを確認してください。
  3. シーケンスが正しい場合、推測します。 そうでない場合は、手順1に戻ります。


最初の段落から始めましょう。このようなランダムなブラケットシーケンスを生成する方法です。 任意のバランスの取れたシーケンスを取り、random.shuffleを介してミックスしましょう。 

  seq = ['(', ')'] * n random.shuffle(seq)


一枚の紙とペンを持って座っている場合、バランスの取れたブラケットシーケンスxには正確に存在することが理解できます。 任意の初期平衡シーケンスをxに変換する順列。 したがって、random.shuffleは、均等な確率でバランスの取れたシーケンスを生成します。 アルゴリズムを取得します。 

 def tryAndCheck(n): seq = [')', '('] * n while (not correct(seq)): random.shuffle(seq) return seq


時間を評価するために残っています。 正しいおよびrandom.shuffleルーチンは1行ごとに機能します。 メインループの反復はいくつになりますか？ 正しいブラケットシーケンスが確率で生成されることがわかっています 。 それから、ワシが確率で落ちるコインがあると言えます 。 マットを計算する必要がありますが、ワシが落ちるまで投げるのを待ちます。



オプションとして、マットをペイントすることもできます。



または、 よく知られている事実を活用してください。 いずれにせよ、マット。 アルゴリズム全体の待機時間は 。



試して修正する



わかりましたが、本当に大きなシーケンスが必要な場合はどうでしょうか？ 100万文字ごとのシーケンス。



線形アルゴリズムはもはやそれほど簡単ではありません。 1992年に、マイク・アトキンソンとジョージ・サックによって別の記事が彼に捧げられました。 ここで、記事に書かれていることについての私のビジョンを提示します。



マジック関数fが必要です。 入力では、関数はバランスのとれたブラケットシーケンスを取り、出力では同じ長さの正しいものを返す必要があります。 関数がシーケンスを均等に分散させること、つまり、すべての通常のシーケンスy に対して 、 f（x）= yのような正確にn + 1のバランスの取れたシーケンスxがあることを確認することが重要です。 関数が線形時間で計算できる場合、ポイントはハット内にあります。



一様分布に従って、括弧で囲まれたバランスのとれたシーケンスxを生成し、f（x）を返します。



関数内のすべてのトリック。 必要に応じて、停止して自分で考え出してみることができます。 機能しません、大丈夫です。 今、私はシリンダーから数学のシリンダーからウサギを取り出し、誰もが大丈夫です。



カウンターがあり、最初はゼロであるとします。 シーケンスを見ていきましょう。 各開き括弧に対して、ポイントを追加し、閉じ括弧ごとに減算します。 

 balance = 0 for c in seq: balance += 1 if c == '(' else -1


下のグラフは、シーケンスに沿って移動するとbalance



カウンターがどのように変化するかを示しています。







別々の色でペイントされたシーケンスは、分解不能と呼ばれます。 つまり 一般に、シーケンスのカウンターが開始点と終了点でのみゼロ値をとる場合、シーケンスは分解できません。 分解できないシーケンスは2つのカテゴリに分類されることに気付くかもしれません：完全にゼロレベルを超えるものと、それ以下のカテゴリです。 前者は正のシーケンスと呼ばれ、後者は負のシーケンスと呼ばれます。



負のサブシーケンスの合計の長さを計算し、半分に分割します。 得られた値はシーケンス欠陥と呼ばれます。 正しいシーケンスの欠陥はゼロです。 長さ2 nの正しいシーケンスのすべてのブラケットを逆のブラケットに置き換えると、欠陥はnになります。



注意、ウサギ！ チャンフェラーの定理。 欠陥kを持つ長さ2 nのブラケットシーケンスの数は、カタロニア語のn番目の数に等しい そしてkに依存しません。



定理は、長さ2 nのすべてのバランスの取れたシーケンスを同じサイズのn + 1クラスに分割し、クラスの中にすべての正しいブラケットシーケンスを含む別のクラスがあるという点で興味深いです。 したがって、欠陥kを持つすべてのシーケンスxを正しいシーケンスyでエンコードする関数を考え出すことができます。この場合、シーケンスyと欠陥kから一意にxを再構築できます。



このような関数を思いついたら、すべての正しいシーケンスに対して 、0からnまでの欠陥とバランスが取れた正確にn + 1が存在することになります。 簡単そうです。



試み1。


すべての負のサブシーケンスを取り、反転します。 ブラケットを反対側に交換します。



そのような機能に加えて、すべての分解不能なシーケンスの位置を保持します。 マイナス-どのサブシーケンスが負で、どのサブシーケンスが正であったかに関するすべての情報を失います。 欠陥が3であることを知っていても、この例から初期シーケンスを復元することはできません。



試行2。


すべての負のサブシーケンスを反転して、最後に配置しましょう。



これで、欠陥がわかったので、負のサブシーケンスを回復できます。 しかし、我々は彼らがいた位置を失いました。



試み3。


任意の分解不可能な負のシーケンスを取り、その極端な括弧を切り取り、結果を逆にします。



このような操作は、unningな反転と呼ばれ、 gで示されます。 シーケンスは分解不能で負なので、結果は常に正しいブラケットシーケンスになります。 関数gの秘Theは、一方では可逆的であり、他方では、負のサブシーケンスの位置をエンコードするために使用できる2つの追加のブラケットがあることです。



試行2を完了したのは、負のシーケンスを逆の順序で取り出し、 g関数を介して巧妙に反転させるだけです。



例からわかるように、負のサブシーケンスの位置は、フリーブラケットで示されます。 私はそれらを青でハイライトし、正方形にしました。 文字eは空のシーケンスを意味します。



どのブラケットが緑色で、どの青色が不良であるかを調べます。つまり、初期シーケンス自体を復元できます。 これが必要なものです！



アトキンソンとサックは、関数fの再帰式を提案しました。



ここに 分解不能なサブシーケンス -残り。



以下に、拡張再帰を使用したPythonのアルゴリズムの実装を添付します。 アルゴリズムが線形時間で実行されることは簡単に理解できます。 

 def tryAndFix(n): seq = ['(', ')'] * n random.shuffle(seq) stack = [] result = [] balance = 0 prev = 0 for pos in range( len(seq) ): balance += 1 if seq[pos] == '(' else -1 if balance == 0: if seq[prev] == '(': result.extend( seq[ prev : pos + 1 ] ) else: result.append('(') stack.append( [ ')' if v == '(' else '(' for v in seq[ prev + 1 : pos ] ] ) prev = pos + 1 for lst in reversed(stack): result.append(')') result.extend(lst) return result




ツリー生成



この場所まで読んでいただければ、とても嬉しいです。 あとは、シーケンスをツリーに変換するだけです。



長さ2 nのブラケットシーケンスは、 n + 1頂点を持つ任意のアリティの木を完全にエンコードします。 実際、詳細な検索を実行します。 上部の入り口で、開始ブラケット、出口で閉じブラケットを書きます。



同時に、 n + 1からの任意のアリティの木は、 n頂点からの二分木と1対1で対応させることができます。 必要なのは、最初に任意のアリティの木を「左の子-右の隣人」の形式で書き留めてから、右の隣人を右の子に名前変更することです。







一緒にいてくれてありがとう！



参照資料





More articles:


All Articles