読者です 読者をやめる 読者になる 読者になる

YAMAGUCHI::weblog

土足で窓から失礼いたします。今日からあなたの息子になります。 当年とって92歳、下町の発明王、エジソンです。

n個の対応する括弧のパターン

Algorithm OCaml

はじめに

ある日Lingrでチャットしてたら@nishioがタイトルで書いたような問題を出していた。たとえば n=1 なら ()、 n=2 なら ()(), (()) という具合。
最初は簡単に解けるっしょ、と思っていたけどこいつが意外と解けない。

基本的な考え方

師曰く、まず何はともあれ次のような方針は常に頭に入れておかないといけないとのこと。

  1. 先にやった処理を再利用する。再利用できる順番でやる。
  2. 規則性がわからないときはシンプルなから列挙して観察する。
  3. 取りこぼしや重複をなくすには端からきっちり順番に数える。
  4. 分離して保管したものを混ぜるのは簡単、混ぜてしまったものを分離するのは大変

重複してしまう

一番最初は開き括弧の位置を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));;

時間かかりすぎ疑惑

師、曰く

あー、これ、OCamlは遅延評価じゃないし純粋でもないよね?解は出ているけど再利用はできてないんじゃないかな?solution 1とかを何度も何度も呼んでない?Pythonでn=12で0m0.888s, n=14で0m3.099sなので、OCamlでそれより遅いのはおかしいんだよ。

コード見てみたら確かにそうなんだよな。とりあえず今はここまで。