はじめに
ある日Lingrでチャットしてたら@nishioがタイトルで書いたような問題を出していた。たとえば n=1 なら ()、 n=2 なら ()(), (()) という具合。
最初は簡単に解けるっしょ、と思っていたけどこいつが意外と解けない。
基本的な考え方
師曰く、まず何はともあれ次のような方針は常に頭に入れておかないといけないとのこと。
- 先にやった処理を再利用する。再利用できる順番でやる。
- 規則性がわからないときはシンプルなから列挙して観察する。
- 取りこぼしや重複をなくすには端からきっちり順番に数える。
- 分離して保管したものを混ぜるのは簡単、混ぜてしまったものを分離するのは大変
重複してしまう
一番最初は開き括弧の位置を2*nからnこ選ぶ問題かなと思ったけど、その場合最後が開き括弧になるものを排除しなければいけなくなって、そのロジックが面倒そうということですぐに却下。
で、n=kのときにn=k-1より前の結果を再利用してやる（規則1)、という考えにはすぐにたどり着きました。問題はここから。
たとえばp(n)を括弧の組み合わせの全パターンとして、*を集合の積とするとp(4)を考えた時には
p(4) = p(1)*p(3) + p(2)*p(2) + p(3)*p(1)
となるかなと簡単に考えていました。しかしこの場合
p(1)*p(3)の1つ --> ()+()(()) p(2)*p(2)の1つ --> ()()+(())
という具合に重複するものが出てしまいます。この重複を排除するのは難しいですね。（規則4）そこでn=1から1つずつ紙に書いてみました。（規則2）
n=1 --> () n=2 --> (()), ()() n=3 --> ((())), (()()), ()()(), ()(()), (())() n=4 --> (((()))), ((()())), (()()()), (()(())), ((())()), ()((())), ()(()()),...
といろいろ書いていった結果、n=kで重複を考えないでいいパターンは ( [n=k-1のときの解] ) であることに気づきます。これを a(k) とします。a(k)以外の解はではどうするか。ここが一番はまったところでした。
重複するときは「なになにA」が「なになにB」だから複数の生成パスができて重複するんであって、「なになにA」を「なになにC」だけに限定したらそもそもそんなことはおきないよね。
穴埋め問題を貰ったわけですが、これがわからん。
師曰く
「分離して保管したものを混ぜるのは簡単、混ぜてしまったものを分離するのは大変」
で、俺はここで行き詰るわけです。
で、師じれったくなって曰く
重複するときは、結合の右辺が分割できるから複数の生成パスができて重複するんであって、結合の右辺を分割できないものだけに限定したらそもそもそんなことはおきないよね。
「取りこぼしや重複をなくすには端からきっちり順番に」
確かに自分が考えてたのは
()()()(())()()
みたいなパターンになったときに重複が起きそうだなあと思ったんだけど、
() + ()()(())()()
にしかなりえないから絶対に重複しない。だから
p(k) = a(k) + s(k)
s(k) = a(i) X p(j) (i+j=k)
ここで演算子 X は左辺と右辺のすべての結合パターンを返す。
実装してみた
let map f l = List.rev (List.rev_map f l);; let enclose x = "(" ^ x ^ ")";; let cross lhs rhs = let rec cross_aux accu = function | [] -> accu | x::xs -> cross_aux (List.fold_left (fun a y -> (x^y)::a) accu rhs) xs in cross_aux [] lhs ;; let rec solution = function | 0 -> [] | n when n < 0 -> prerr_int n; invalid_arg "solution" | n -> List.rev_append (atomic n) (separate n) and atomic = function | 1 -> ["()"] | n -> map enclose (solution (n-1)) and separate n = let rec separate_aux accu = function | 0 -> accu | k -> separate_aux (List.rev_append (cross (atomic k) (solution (n-k))) accu) (pred k) in separate_aux [] (n-1) ;; Printf.printf "%d\n%!" (List.length (solution 14));;
