Partition Function

今日は大晦日。また新しい年が来る。来年は、個人的には大変良い年となる。
さて、ゴルフ。

なかなか面白い問題だったと思う。wikipedia 等より、Partition Function p(n) は以下のように表されることがわかる。

P(k,n)=0 if k>n                    -- (1)
P(k,n)=1 if k==n                   -- (2)
P(k,n)=P(k+1,n)+P(k,n-k) otherwise -- (3)

p(n)=P(1,n)                        -- (4)

これより、横軸を k 、縦軸を n に対応させて N x N の行列を考えると、第 1 列が Partition Function となる。(1) より、行列の右上半分は 0 となり、(2) より対角線要素は 1 である。行列の左下半分を (3) の式により対角線要素から左に向かって、つまり、k が小さくなる方向へ計算して行き、k==1 (左端)となったところが求める、Partition Function p(n) の値となる。C で書くと、

p[99][100];n;
main(k,a){
    for(;a=n++<100;printf("p(%d)=%d\n",n,a))
        for(k=n;k;)p[k][n]=a+=p[k][n-k--];
}

100 x 100 の行列を配列として確保し、1 行目から順に値を求めていく(外側の for 文)。各行においては、対角要素から左に向かって計算して行く(内側の for 文)。対角要素は常に 1 なので、変数 a を 1 で初期化し、その a に、上記 (3) 式の右辺の第 2 項を足すことで、1 つ左の項を求めている。このまま、左端の列まで計算すると、a の値が Partition Function の値となるので、それを出力している。
〜〜〜
さて、新たに、endless 問題として、Paths in matrix と Paths in matrix 2 を出題した。どちらも、最近、地下鉄の日能研の広告(http://www.nichinoken.co.jp/column/shikakumaru/2012/1212_sa.html)に出ていた問題からヒントを得たものである。この日能研の問題は、中学の入試問題だそうだ。すごいな。小学生がこんな問題解けるのか。特に問 2 の合計が 70 になる道順が何通りあるかなんて、結構難しいと思う。でも、小学生に解けるのだから、golfer なら簡単だろう。
問題はちょっとアレンジしてある。Paths in matrix は、単純に正方行列の左上から右下への道順の個数を求めるというもの。ヒントになってしまうが、この問題を考えていた時、以下に気が付いた。行列のある位置、(i, j) に関して考えると、この位置に来る道順の個数は、上 (i, j-1) から来るものと、左 (i-1, j) から来るものの和であるということが言える。これって、行列を 45 度右に回転して頂点から見ていくと、パスカルの三角形じゃん！っということになる。漸化式で書くと、

p(n)=P(n,n)=P(n-1,n)+P(n,n-1)

Partition Function ともちょっと似てたな。
Paths in matrix 2 は、もろ、日能研の問 2 の汎化。合計が 70 だけではなく、golfer なら、すべての合計値に対して道順の数くらい数えられるだろう、という問題である。頑張ってください。
〜〜〜
では、よいお年を。

2013/1/1追記

Paths in matrix は、411. PATHS と同じだった。記憶から消えてた。まぁ、でも、今回のは、output が 32bit int のレンジに入っているので、より多くの言語で解きやすいだろう。

2013/1/3追記

Paths in matrix 2 について。
はじめの数項をみると、Partition function と同じだ。前述日能研のページの解説にもあるが、すべての道順は、1〜10 の数を最低 1 回は使う。なので、その分を差し引くと、道順の全 19 ポジション(通過する行列要素)の内、残り 9 ポジションに、1〜10 の数をどう配置するかで道順は決まることになる。たとえば、9 ポジションすべて 1 とすると、合計が 64 の道順になる。8 個の 1 と 1 個の 3 とすると、合計が 66 の道順として＊確定＊する。以下のよう。

1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 10  # 9 個の 1。合計：64
1 1 1 1 1 1 1 1 1 2 2 3 4 5 6 7 8 9 10  # 8 個の 1 と 1 個の 2。合計：65
1 1 1 1 1 1 1 1 1 2 3 3 4 5 6 7 8 9 10  # 8 個の 1 と 1 個の 3。合計：66

これは、つまり、64 との差を 1〜10 の数字 9 個の和として表す表し方である。また、その表し方の個数が求めるものとなる。この 9 個という制限は、9 個の 1 との差分で考えると、2 〜 10 の数字の 9 個以下の和で表す表し方、と言い換えることができ、さらに、この使う数も 1 との差分で考えると、結局、以下のように問題を再定義することができる。

自然数 N を 1 〜 9 の自然数の最大 9 個の和であらわす表し方はいくつあるか？

これは、N が 9 より小さいときは、おのずと「1 〜 9 の自然数」、「最大 9 個」という制限は成立するので、この範囲では、自然数 N に対する Partition Function と一致するということになる。なので、本問のはじめの数項は、Partition Function と一致したということだ。
なんだか、新しい問題を作ったつもりだったのだが、結局 Partition Function のバリエーションにすぎなかったということか。とはいえ、N > 9 の時の制限をどう解決するかは、それはそれで難しそうだな。

2013/1/4追記

Partition Function の補助関数 P(k,n) は、自然数 n を k 以上の自然数の和に分割する方法の個数だった。wikipedia にもそう書いてあった。P(n,n) が 1 なのは、n は n としてしか表せないからであり、また、P(1,n) が Partition Function となるのは、1 以上の自然数の和で表す個数なので、定義そのものである。この点を考慮すると、昨日の追記で書いた制限「1 〜 9 の自然数」という点は、

P(k,n)=0 if k>9

という条件を足してやればよいのではないか？(k,n) の行列で言うと、k 列より右はすべて 0 ということ。これなら簡単に計算できそうだ。
残すは、「最大 9 個」という制限だ。こちらは、P(k,n) の再帰の深さに対応しそうな気がする。ちょっとやってみるか。

2013/1/4追記2

できたことはできたが、120B と短くならなかった。

p(k,n,d){return n?d>9|k>9|k>n?0:k<n?p(k+1,n,d)+p(k,n-k,d+1):1:1;}
n;main(){for(;n<82;)printf("%d:%d\n",++n+63,p(1,n,1));}

もう少しチューニング可能かな？