无递归PARI/GP算法生成反字典序分拆：求替代算法及性能评估

想必大家对分拆（partition）及其表示方式（如字典序及其变体）并不陌生。以下是一些**反字典序（co-lexicographic order）**的分拆示例：

[1]

[1, 1]
[2]

[1, 1, 1]
[2, 1]
[3]

[1, 1, 1, 1]
[2, 1, 1]
[3, 1]
[2, 2]
[4]

[1, 1, 1, 1, 1]
[2, 1, 1, 1]
[3, 1, 1]
[2, 2, 1]
[4, 1]
[3, 2]
[5]

不难发现其中规律：我们只需基于如下分拆：

[1]
[2]
[3]
[2, 2]
[4]
[3, 2]
[5]

对于n的特定分拆，只需将其与若干个1组成的向量拼接，其中1的数量等于n减去该分拆所有部分的和。该思路并非首创（参考OEIS序列A210941）。

需求是无递归生成A210941的指定行，我已编写了一个无递归的高效PARI/GP算法，代码如下：

\ Main function is list(vec).
\ Input is a vector of the indices k.
\ Output is a vector of the corresponding partitions.
\ Here b4(k) is computed without recursion.
\ So this program is good when you need to compute a few number of partitions.
\ Especially when k is large.

b1(n) = {my(A = 1, B, v1); v1 = [1];
until(v1[A]>n, v1 = concat(v1, 0); B = 1;
while((binomial(B+1, 2) - binomial(B\2+1, 2)) <= A,
v1[A+1] += (-1)^((B-1)\2)*v1[A - binomial(B+1, 2) + binomial(B\2+1, 2) + 1]; B++); A++);
A-1}
list(vec) = {my(b2(n) = my(v1);
v1 = vector(n, i, vector(i\2+1, j, i==1));
for(i = 2, n, v1[i][i\2+1] = 1; v1[i][1] = vecsum(v1[i-1]);
for(j = 2, i\2, v1[i][j] = v1[i-1][j-1] - if((i-j) >= 2*(j-1), v1[i-j][j-1])));
for(i = 2, n, forstep(j = i\2, 1, -1, v1[i][j] += v1[i][j+1]));
v1,
vv1 = b2(b1(vecmax(vec))),
b3(n) = my(A = 0); until(vv1[A][1] > n, A++); A-1,
b4(n) = my(A = b3(n),
n = if(n == vv1[A][1], n, vv1[A][1] + vv1[A+1][1] - n),
B = n - vv1[A][1], C, v1);
v1 = []; while(!(B == 0), C = 1;
until(vv1[A+1][C]<=B, C++); v1 = concat(v1, C-1);
n -= vv1[A][1] - vv1[A - C + 1][1] + vv1[A+1][C];
A = b3(n); B = n - vv1[A][1]); v1 = Vecrev(v1);
v1 = concat(A + (#v1 > 0), v1));
vec = vector(#vec, i, b4(vec[i]))}

我需要评估该算法的速度，为此需进行对比，因此寻求替代的无递归算法；若无相关思路，也请对该算法的速度给出评价。

内容的提问来源于stack exchange，提问作者user23886965