分配整数数组按比例补偿舍入误差 [英] Allocate an array of integers proportionally compensating for rounding errors

问题描述

予具有非负值的阵列。我想建立值的数组谁的总和是20，使得它们成比例的第一阵列

I have an array of non-negative values. I want to build an array of values who's sum is 20 so that they are proportional to the first array.

这将是一个简单的问题，但我想比例阵列来概括准确 20，补偿任何舍入误差。

This would be an easy problem, except that I want the proportional array to sum to exactly 20, compensating for any rounding error.

例如，阵列

input = [400, 400, 0, 0, 100, 50, 50]

将产生

output = [8, 8, 0, 0, 2, 1, 1]
sum(output) = 20

然而，大多数情况下，将有大量的舍入误差，如

However, most cases are going to have a lot of rounding errors, like

input = [3, 3, 3, 3, 3, 3, 18]

天真地产生

output = [1, 1, 1, 1, 1, 1, 10]
sum(output) = 16  (ouch)

有没有分摊输出数组，这样加起来20的好办法，每次？

Is there a good way to apportion the output array so that it adds up to 20 every time?

推荐答案

所以上面的答案和意见是有益的......特别是从@Frederik下降的总和评论。

So the answers and comments above were helpful... particularly the decreasing sum comment from @Frederik.

我想出了解决方案利用了这样一个事实：一个输入数组V，和（V-I * 20）整除之和（V）。因此，对于在v中的每个值，我mulitply 20和除以相加。我把商，积累的剩余部分。每当累加器大于总和（v）中，我加一的值。这样，我保证，所有的余数得到滚入结果。

The solution I came up with takes advantage of the fact that for an input array v, sum(v_i * 20) is divisible by sum(v). So for each value in v, I mulitply by 20 and divide by the sum. I keep the quotient, and accumulate the remainder. Whenever the accumulator is greater than sum(v), I add one to the value. That way I'm guaranteed that all the remainders get rolled into the results.

是清晰？下面是用Python实现：

Is that legible? Here's the implementation in Python:

def proportion(values, total):
    # set up by getting the sum of the values and starting
    # with an empty result list and accumulator
    sum_values = sum(values)
    new_values = []
    acc = 0

    for v in values:
        # for each value, find quotient and remainder
        q, r = divmod(v * total, sum_values)

        if acc + r < sum_values:
            # if the accumlator plus remainder is too small, just add and move on
            acc += r
        else:
            # we've accumulated enough to go over sum(values), so add 1 to result
            if acc > r:
                # add to previous
                new_values[-1] += 1
            else:
                # add to current
                q += 1
            acc -= sum_values - r

        # save the new value
        new_values.append(q)

    # accumulator is guaranteed to be zero at the end
    print new_values, sum_values, acc

    return new_values

（我补充说，如果累加器>部分，我增加当前值的previous值，而不是增强）

(I added an enhancement that if the accumulator > remainder, I increment the previous value instead of the current value)

这篇关于分配整数数组按比例补偿舍入误差的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！