整数の分割の列挙（2）

整数の分割は、別の表現もできる。
例えば、
4 4 2
なら、
1が0個、2が1個、3が0個、4が2個、
だから、
0 1 0 2
とも表現できる。
こうすると、例えば、
4 1 1 1 1 1 1 1 1
が
8 0 0 1
となって、短くて済み、
最初に1でないものを見つけるのが速い。

これで、344msが62msとなった。

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) {

    // 0でない要素を探す

    var pos;

    var sum = ary[1];

    var length = ary.length;

    for(pos = 2; pos < length; pos++) {

        if(ary[pos] > 0)

            break;

    }

    if(pos == length)       // 全て0

        return false;

    

    ary[pos]--;

    sum += pos;

    pos--;

    var mod = sum % pos;

    ary[1] = 0;

    ary[pos] = (sum - mod) / pos;

    if(pos > 1)

        ary[mod] = 1;

    return true;

}
function initDiv(length, max) {

    var ary = [ ];

    if(length < max)

        max = length;

    for(var i = 0; i <= max; i++)

        ary.push(0);

    

    var mod = length % max;

    ary[mod] = 1;

    ary[max] = (length - mod) / max;

    

    return ary;

}
function print(str) {

    WScript.Echo(str);

}