n 個の括弧シーケンスは、n 個の "("s および n ")" で構成されます。
有効な括弧のシーケンスは、次のように定義されています。
隣接する括弧「()」が空になるまで消去を繰り返す方法を見つけることができます。
たとえば、「(())」は有効な括弧です。2 番目と 3 番目の位置のペアを消去して「()」にしてから、空にすることができます。")()(" は有効な括弧ではありません。2 番目と 3 番目の位置のペアを消去すると、")(" になり、それ以上消去できなくなります。
これで、有効な n 個の括弧のシーケンスがすべて揃いました。辞書順で k 番目に小さいシーケンスを見つけます。
たとえば、次のすべての有効な 3 つの括弧のシーケンスを辞書順で示します。
((()))
(()())
(())()
()(())
()()()
ソース: https://code.google.com/codejam/contest/4214486/dashboard#s=p3
注: コンテストは現在終了しており、ソリューションをダウンロードできます。
C++ STL で利用可能な next_permutation() を使用して、小さい入力 ( k < 10 6 ) について解決しました。このためのサブ問題を定式化することはできません。カタロニア語の番号を使用してこれを解決しようとしましたが、成功していないようです。学習に役立たないので、解決策を見たくありません。サブの問題を特定するのを手伝ってください。