重新缩放整数向量

Question

假设我有一个正整数的向量V. 如果整数之和大于正整数N,我想重新调整V中的整数,使得和<= N.V中的元素必须保持在零以上.V的长度保证<= N.

是否有算法在线性时间内执行此重新缩放？

这不是功课,BTW :).我需要从符号到符号频率重新缩放地图以使用范围编码.

一些快速思考和谷歌搜索没有给出问题的解决方案.

编辑:

好的,这个问题有点不清楚."重新缩放"表示"标准化".也就是说,将V中的整数(例如乘以常数)转换为较小的正整数,从而满足sum(V)<= N的标准.保留整数之间的比率越好,压缩效果越好.

问题是以这种方式开放式的,该方法不需要找到保持比率的最佳(例如,最小二乘拟合感觉)方式,而是"良好"的方式.如建议的那样,将整个向量设置为1是不可接受的(除非强制).例如,"好"足以找到满足求和标准的最小除数(定义如下).

以下天真算法不起作用.

1. 找到当前的总和(V),Sv
2. 除数:= int(ceil(Sv/N))
3. 用除数除以V中的每个整数,向下舍入,但不小于1.

这在v = [1,1,1,10]时失败,N = 5.

divisor = ceil(13 / 5) = 3.
V := [1,1,1, max(1, floor(10/3)) = 3]
Sv is now 6 > 5.

在这种情况下,正确的归一化是[1,1,1,2]

一种可行的算法是对除数(上面定义)进行二元搜索,直到找到满足求和标准的[1,N]中的最小除数.从ceil(Sv/N)开始猜测.然而,这在操作次数上不是线性的,而是与len(V)*log(len(V))成比例.

在一般情况下,我开始认为在线性时间内做不好.我可能会采用某种启发式方法.

Answer 1

只需将所有整数除以它们的最大公约数即可。您可以通过多次应用欧几里得算法来有效地找到 GCD 。

d = 0
for x in xs:
    d = gcd(d, x)

xs = [x/d for x in xs]

积极的一点是，通过这种方式，您总是可以得到尽可能小的表示，而不会放弃任何精度，也不需要选择特定的 N。缺点是，如果您的频率是很大的互质数，您将别无选择，只能牺牲精度（并且您没有指定在这种情况下应该做什么）。

Answer 2

我认为你应该重新缩放 1 以上的部分。因此，从所有值中减去 1，并从 N 中减去 V.length。然后正常重新缩放，然后加回 1。如果您不断计算总计，而不是只选择一个因素，您甚至可以做得更好，这通常会浪费一些“数字空间”。像这样的东西：

public static void rescale(int[] data, int N) {
    int sum = 0;
    for (int d : data)
        sum += d;

    if (sum > N) {
        int n = N - data.length;
        sum -= data.length;

        for (int a = 0; a < data.length; a++) {
            int toScale = data[a] - 1;
            int scaled = Math.round(toScale * (float) n / sum);

            data[a] = scaled + 1;
            n -= scaled;
            sum -= toScale;
        }
    }
}