tmp.py 解説

昨日捨てるのが惜しいからとブログに貼ったtmp.pyだけども、何をしているのか気になるという話があったので簡単に解説。

まずnを小さくして、あとprint文が説明なしで整数を表示していて分かりにくいのでいじって実行するとこういう出力が出る

n: 2
(())
()()
2

n: 3
((())), (()())
()(()), ()()(), (())()
5

n: 4
(((()))), ((()())), (()(())), (()()()), ((())())
()((())), ()(()()), ()()(()), ()()()(), ()(())(), (())(()), (())()(), ((()))(), (()())()
14

n: 5
((((())))), (((()()))), ((()(()))), ((()()())), (((())())), (()((()))), (()(()())), (()()(())), (()()()()), (()(())()), ((())(())), ((())()()), (((()))()), ((()())())
()(((()))), ()((()())), ()(()(())), ()(()()()), ()((())()), ()()((())), ()()(()()), ()()()(()), ()()()()(), ()()(())(), ()(())(()), ()(())()(), ()((()))(), ()(()())(), (())((())), (())(()()), (())()(()), (())()()(), (())(())(), ((()))(()), ((()))()(), (()())(()), (()())()(), (((())))(), ((()()))(), (()(()))(), (()()())(), ((())())()
42

これは「対応が取れている括弧」が何通りあるか列挙している。() はありだけど )( は開く前に閉じているからNG、((()))はありだけど())(()は開く前に閉じているからNG、ということ。
で、それをどうすれば効率よく求められるか、という話でn=5の時の計算はn=4以下の時を再利用して楽に済ませたいよね、というわけでmemに過去の履歴を覚えてある。ただ何も区別せずに覚えると()()と()をくっつけて()()()ってのと、()と()()をくっつけて()()()ってのみたいに重複が出てしまって取り除くのが大変なので「ひとかたまりになっているもの」と「わかれているもの」は分けて記憶している。くっつける左側をひとかたまりのもの限定にすれば重複が起きないからね。