典型02の条件評価・ループをシンプルに

問題

((()()))のようなネストとした括弧で文字数が入力と等しいもののリストを辞書順に出力する問題

例:
入力 6
出力
( ( ( ) ) )
( ( ) ( ) )
( ( ) ) ( )
( ) ( ( ) )
( ) ( ) ( )

解１ bit全探索

1から順に全探索する場合、ループカウンタが以下の制約を満たすかチェックする必要がある

1の数 = 入力の値 / 2
入力の値以下の任意の桁に対して「その桁以右の0の数<=1の数」

反対に、以下は保証されているので調べなくてよい

括弧の辞書順

解２ 組み合わせ全探索

以下の記事のnext_combination関数をループ処理に用いた場合、
ループカウンタが以下の制約を満たすかチェックする必要がある
入力の値以下の任意の桁に対して「その桁以右の0の数<=1の数」

以下は保証されているので調べなくてよい
括弧の辞書順
1の数 = 入力の値 / 2

解３ 条件付組み合わせ探索

上記next_combination関数を応用し、今回の問題にフィットした組み合わせを返す関数を以下のように作る
この関数が返す値は
1の数 = 入力の値 / 2 かつ 入力の値以下の任意の桁に対して「その桁以右の0の数<=1の数」 を満たす整数で、
入力の整数の次に大きいもの（->辞書順）である
したがって、この関数を使うとループカウンタが常に制約を満たすので関数呼び出し元で条件評価をする必要がなくなる

int next_bracket(int sub){
  int th = 0b1010101010101010101010101010101010;
  int x = sub & th, y = x & -x;
  if(!x)return 0;
  if(!(y>>3))return next_combination(sub);
  int d = (log2(y)-1)/2, ad = sub & (y>>1)*3, cf = sub +(ad & -ad);
  return (-(~sub & cf)& cf) | (((((sub & ~cf)/y)+1)<<d) -1);
}

解説

  int th = 0b1010101010101010101010101010101010;
  int x = sub & th, y = x & -x;
  if(!x)return 0;
  if(!(y>>3))return next_combination(sub);

厳密な証明はしていないが、引数に対してnext_combination関数を呼び出して得られる次の組み合わせ整数表現が制約を満たさないとき、決まって引数の末尾2桁は01つまり( )になっている
引数の末尾2桁が01かどうかを知るために、後の処理でも使うyに1010...1010と引数で共有する一番下の位の1を入れ、これをnext_combination関数を使っていいか否かの判断に使っている
末尾が01以外（といっても11しかないが）の場合、yを2,3回右シフトするとyつまり10は彼方に消えるので4行目が実行される

  int d = (log2(y)-1)/2, ad = sub & (y>>1)*3, cf = sub +(ad & -ad);
  return (-(~sub & cf)& cf) | (((((sub & ~cf)/y)+1)<<d) -1);

dは引数末尾に連続している01の個数
cfは引数末尾の連続した01を除いて一番末尾にある1を探し当て(ad&-ad)、引数にそれを足した値。
cfの末尾01除く1と(返り値|の左)、
subにad&-adを足してなくなった1の個数＋dだけ右から1を詰たもの(返り値|の右)の論理和を取ると目当ての組み合わせ整数表現になる

補足と注意

一応この関数を使ったループでACは出ましたが、前半部分も後半部分も厳密な証明はしていないので論理的には誤っている可能性があります。
筆者灰Coderですが、初見解法２で20分弱に対して解法３の実装に3時間強かかったので、似たような問題で条件が異なる場合にも使えるような一般性のある解法ではありません。ビット演算に対する相当な慣れがあれば違うのかもしれませんが。
dの計算にlog2関数を使用していますが、yは2の累乗であることが保障されるので右シフトを使ったwhileループや二分探索で計算したほうが早いかもしれません

最後に感想

けんちょんさん(作？)のnext_combination関数が大好きなので自分でも似たようなの作りたいだけでやってみました。
条件分岐や他の関数使ってたりビット演算が元と比べて煩雑だったりするので、本家の凄さを改めて感じました。
オサレ度はまだまだですが、ちゃんとAC出るような、思ったような処理を複雑なビット演算を使ってできたので個人的には満足です。
この記事をご覧の皆さんも、ビット探索のループ処理をビット演算を使ってカスタマイズしてみてはいかがでしょうか。
最後までご覧いただきありがとうございました。