求Pari/GP下生成剔除旋转重复的定长定和正整数向量的最优算法

核心思路 #

不需要生成全量候选后再去重，直接生成每个旋转等价类的唯一代表元即可：我们约定每个等价类取字典序最小的向量作为唯一代表，生成时仅保留符合该条件的向量，大幅降低无效计算量。

伪算法 #

输入：长度参数N，和参数S
输出：所有互不旋转等价的符合要求的正整数向量列表

• 初始化空结果列表
• 遍历向量最小元素的可能取值m，范围为1 ≤ m ≤ floor(S/N)（所有元素≥m时总和不能超过S）
• 对每个m，生成所有长度为N-1、元素≥m、和为S - m的正整数向量，拼接m作为首元素得到完整候选向量E
• 验证E是否为自身所有旋转中的字典序最小值：遍历所有偏移量生成旋转后的向量，若存在任意旋转向量小于E则丢弃，否则加入结果列表
• 最终返回结果列表

Pari/GP 原生实现 #

利用Pari/GP内置的forvec函数高效生成满足范围约束的向量，代码如下：

rot_min_vectors(N, S) = {
    my(res = List());
    \\ 遍历等价类代表元的最小元素m
    for(m = 1, S\N,
        my(T = S - m, off = m - 1);
        my(target = T - off*(N-1));
        \\ 剩余N-1个元素为≥m的正整数，等价于减off后≥1，和为target
        if(target < N-1, next);
        \\ 生成所有符合和要求的向量
        forvec(v = vector(N-1, i, [1, target - (N-2)]),
            if(sum(i=1, N-1, v[i]) == target,
                my(E = concat([m], vector(N-1, i, v[i] + off)));
                my(is_min = 1);
                \\ 校验是否为旋转最小
                for(k = 1, N-1,
                    my(rot = concat(E[k+1..N], E[1..k]));
                    if(rot < E, is_min = 0; break);
                );
                if(is_min, listput(res, E));
            )
        , 1);
    );
    return(Vec(res));
}

验证说明 #

• 调用#rot_min_vectors(4,7)可得到过滤后的结果，会自动排除[1,1,3,2]这类旋转等价项
• 调用#rot_min_vectors(4,16)返回值为116，完全匹配给定的验证数据

可选高阶优化 #

如果需要处理更大的N、S，可以直接使用项链（Necklace）枚举算法，该类算法可以直接生成所有旋转等价类的代表元，不需要额外校验旋转，效率更高。

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