分配一个整数数组，按比例补偿舍入误差

我有一个非负值数组。我想建立一个和为20的值的数组，以便它们与第一个数组成比例。

这将是一个简单的问题，除了我希望比例数组的和恰好20，补偿任何舍入误差。

例如，数组

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

将产生

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

然而，大多数情况下会有很多舍入错误，比如

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

天真的收益率

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

是否有一种很好的方法来分配输出数组，使其每次相加为20 ?

这个问题的答案很简单:我已经做过很多次了。每次赋值到新数组之后，您都要减少正在处理的值，如下所示:

调用第一个数组A，和新的，成比例的数组B(开始为空)。
调用A元素的和T
调用所需的和s
对于数组的每个元素(i)执行以下操作:
。B[i] = round(A[i]/T * S).(四舍五入到最接近的整数，便士或任何要求)
b。T = T - A[i]
c。S = S - B[i]

就是这样!易于在任何编程语言或电子表格中实现。

解决方案是最优的，因为结果数组的元素与理想的非舍入值的距离永远不会超过1。让我们用你的例子来证明:
T = 36, S = 20。B[1] = round(A[1]/T * S) = 2。(理想情况下,1.666…)
T = 33, S = 18。B[2] = round(A[2]/T * S) = 2。(理想情况下,1.666…)
T = 30, S = 16。B[3] = round(A[3]/T * S) = 2。(理想情况下,1.666…)
T = 27, S = 14。B[4] = round(A[4]/T * S) = 2。(理想情况下,1.666…)
T = 24, S = 12。B[5] = round(A[5]/T * S) = 2。(理想情况下,1.666…)
T = 21, S = 10。B[6] = round(A[6]/T * S) = 1。(理想情况下,1.666…)
T = 18, S = 9。,B[7] = round(A[7]/T * S) = 9。(理想情况下,10)

请注意，将B中的每个值与括号中的理想值进行比较，差值永远不会大于1。

还值得注意的是，重新排列数组中的元素可能会导致结果数组中对应的值不同。我发现按升序排列元素是最好的，因为这样可以使实际和理想之间的平均百分比相差最小。

你的问题类似于比例代表制，你想在政党之间按比例分享N个席位(在你的情况下是20个)，在你的情况下[3,3,3,3,3,3,18]

在不同的国家有几种处理舍入问题的方法。我下面的代码使用了瑞士使用的Hagenbach-Bischoff配额方法，该方法基本上将整数除以(N+1)后剩余的席位分配给具有最高余数的政党:

def proportional(nseats,votes):
    """assign n seats proportionaly to votes using Hagenbach-Bischoff quota
    :param nseats: int number of seats to assign
    :param votes: iterable of int or float weighting each party
    :result: list of ints seats allocated to each party
    """
    quota=sum(votes)/(1.+nseats) #force float
    frac=[vote/quota for vote in votes]
    res=[int(f) for f in frac]
    n=nseats-sum(res) #number of seats remaining to allocate
    if n==0: return res #done
    if n<0: return [min(x,nseats) for x in res] # see siamii's comment
    #give the remaining seats to the n parties with the largest remainder
    remainders=[ai-bi for ai,bi in zip(frac,res)]
    limit=sorted(remainders,reverse=True)[n-1]
    #n parties with remainter larger than limit get an extra seat
    for i,r in enumerate(remainders):
        if r>=limit:
            res[i]+=1
            n-=1 # attempt to handle perfect equality
            if n==0: return res #done
    raise #should never happen

然而，这种方法并不总是像你这样完全平等地给予相同数量的席位:

proportional(20,[3, 3, 3, 3, 3, 3, 18])
[2,2,2,2,1,1,10]

您设置了3个不兼容的需求。与[1,1,1]成比例的整数值数组不能恰好等于20。您必须选择打破"总和恰好为20"，"与输入成比例"one_answers"整数值"要求中的一个。

如果您选择打破整数值的要求，则使用浮点数或有理数。如果您选择打破精确的总和要求，那么您已经解决了问题。选择打破比例是有点棘手的。您可能采取的一种方法是计算出您的和偏离了多远，然后在输出数组中随机分配更正。例如，如果您的输入是:

[1, 1, 1]

那么你首先可以使它尽可能地和，同时仍然是成比例的:

[7, 7, 7]

，从20 - (7+7+7) = -1开始，选择一个元素随机递减:

[7, 6, 7]

如果错误是4，您将选择四个元素进行递增。

一个性能不佳，但会提供正确结果的naïve解决方案…

编写一个迭代器，给定一个包含8个整数的数组(candidate)和input数组，输出与其他元素成比例最大的元素的索引(伪代码):

function next_index(candidate, input)
    // Calculate weights
    for i in 1 .. 8
        w[i] = candidate[i] / input[i]
    end for
    // find the smallest weight
    min = 0
    min_index = 0
    for i in 1 .. 8
        if w[i] < min then
            min = w[i]
            min_index = i
        end if
    end for
    return min_index
 end function

然后执行

result = [0, 0, 0, 0, 0, 0, 0, 0]
result[next_index(result, input)]++ for 1 .. 20

如果没有最优解，它将向数组的开头倾斜。

使用上面的方法，您可以通过舍入来减少迭代次数(就像您在示例中所做的那样)，然后只使用上面的方法来添加由于舍入错误而遗漏的内容:

result = <<approach using rounding down>>
while sum(result) < 20
    result[next_index(result, input)]++

所以上面的答案和评论很有帮助…特别是来自@Frederik的递减求和评论。

我提出的解决方案利用了这样一个事实，即对于输入数组v, sum(v_i * 20)可以被sum(v)整除。对于v中的每一个值，我乘以20，然后除以和。我保留商，把余数加起来。每当累加器大于sum(v)时，我将值加1。这样，我就可以保证所有的余数都包含在结果中。

清楚吗?下面是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

(我增加了一个增强，如果累加器>余数，我增加前一个值而不是当前值)

相关内容

最新更新

热门标签：