例えば, 5つの数1,2,3,4,5を並び替えた3,1,5,2,4の場合, 単調増加な部分列で最長のものが1,2,4で単調減少な部分列で最長のものは3,1や3,2、5,2や5,4。したがってこの場合の最長なものの長さは3です。
そのままの1,2,3,4,5なら5となります。
「Erdös Szekersの定理」により, n^2+1個の相違なる数を並べ替えた場合, 必ずn以上の長さの単調増加か単調減少な部分列があるわけですが, それらの「長さ」の分布が気になって調べてみようとプログラムを組んで数えさせてみました。
普段プログラムはこのような「気になることを一寸調べる」程度でしか使わないので技術も知識も乏しく工夫のないプログラムになることが多くその上正しく動いているのかどうかも分からない場合があり, 今回もそのような感じです。
例えば, 3^2+1で10個の数を並び替えた場合の分布が
0, 0, 0, 0, 985032, 1969348, 592652, 76562, 5042, 162, 2
と出たのですが... 果たしてこれで良いのか。
rubyで組んで
[Done] exited with code=0 in 157.134 seconds
と少々時間が掛かり, これ以上は時間が相当掛かりそうです。
そこで質問です。
- 上手いアルゴリズム、プログラミングの手法があるでしょうか。
- それ以前にこの「数え上げ」は正しいでしょうか。
教えて下さると有難いです。
sum(0, 0, 0, 0, 985032, 1969348, 592652, 76562, 5042, 162, 2) == 3628800 == 10!
なので、総数は合致していますね。