按词典顺序划分（无递归的 PARI/GP 算法）

Question

你们中的许多人可能都熟悉分区及其表示方式（我的意思是字典顺序及其变体）。

以下是一些按字典顺序排列的分区：

[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 减去给定分区所有部分的总和。

这个想法并不新鲜（参见A210941）。

问题是在没有递归的情况下生成 A210941 的给定行。

我尝试编写一种无需递归即可工作的高效算法，这就是我得到的：

\\ 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]))}

我需要评估这个算法的速度。为此，需要将其与某些东西进行比较，因此我对无需递归的替代算法感兴趣。

如果您对替代算法没有任何想法，请在评论中写下您如何评价我的算法的速度。

Answer 1

我没有替代算法来进行基准测试（今晚下班后我会尝试想出一些东西），但我可以提供一种方法来分析算法的效率。评论有点太长了，抱歉。

我们可以做的是，在样本输入分布广泛的情况下，凭经验估计解决方案的时间复杂度。首先针对各种输入值运行算法

n

，并测量其运行时间

t

，从小规模开始并将输入加倍，直到开始运行时间过长（这可能是几秒或几分钟，具体取决于您的耐心）。

取出这些

n

/

t

对的表格，并将它们绘制在双对数图上。然后，通过您的点找到一条最佳拟合线（您可能想要丢弃较小的

n

值，因为它们会很吵，并且会因低阶项而倾斜）。

如果您的算法的时间复杂度约为

O(n^a)

，则

t ~= c * n^a + b

表示较大的

n

。取两边的对数，

log(t) = log(c * n^a + b)

，但是

n^a

项会冲掉足够大的

n

的常数项，所以我们放弃它：

log(t) = log(c * n^a) = log(c) + a * log(n)

。您可以看到这是一个用

log(t)

和

log(n)

表示的线性方程，这正是我们绘制的图形。最佳拟合线的斜率（大约）是观察到的时间复杂度，截距是常数因子的对数。当然，这假设您有足够大的样本点，观察到的时间反映了真实的时间复杂度，并且时间复杂度是多项式（不包括对数因子）。

如果你相信你的算法本质上是指数的，你仍然可以使用这个技巧，但你有

log(t) = log(c * a^n) = log(c) + log(a) * n

，所以只取时域上的对数，然后你的底数

a

就是你的斜率的exp。