整数の分割の列挙というのは、
例えば5だったら、
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
というもの。
アルゴリズムは簡単で、
次の分割を得るには、
右から探して最初に1でないものを見つけて、
そこから1を引く。
そして、その数字を最大にして、残りを分割する。
全部1になったら終わり。
ここでは、
分割後の最大の数を指定して、分割を列挙するプログラムを示す。
100を最大4で分割で、344msかかった。
var t0 = (new Date()).getTime();
var counter = 0;
var d = initDiv(100, 4);
do {
counter++;
// print(d);
} while(nextDiv(d));print(counter);
print( (new Date()).getTime() - t0);function nextDiv(ary) {
// 1でない要素を後ろから探す
var pos;
var sum = 0;
for(pos = ary.length - 1; pos >= 0; pos--) {
var a = ary[pos];
sum += a;
if(a != 1)
break;
}
if(pos == -1) // 全て1
return false;
var max = --ary[pos];
sum -= max;
for(pos++; ; pos++) {
if(sum <= max) {
ary[pos] = sum;
ary.length = pos + 1;
return true;
}
else {
ary[pos] = max;
sum -= max;
}
}
}function initDiv(length, max) {
var ary = [ ];
while(true) {
if(length <= max) {
ary.push(length);
return ary;
}
else {
ary.push(max);
length -= max;
}
}
}function print(str) {
WScript.Echo(str);
}
