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

Question

我有一组非负值.我想构建一个值为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个？

Answer 1

您的问题类似于比例代表,您希望在他们获得的选票中按比例分享N个席位(在您的情况下为20个),在您的情况下[3,3,3,3,3,1,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]

Answer 2

对这个问题有一个非常简单的答案:我已经多次完成了这个问题.每次分配到新数组后,您将减少您正在使用的值,如下所示:

1. 调用第一个数组A和新的比例数组B(开始为空).
2. 调用A元素T的总和
3. 调用所需的金额S.
4. 对于阵列(ⅰ)中的每个元素执行以下步骤:
   一.B [i] = round(A [i]/T*S).(舍入到最接近的整数,便士或任何需要的东西)
   b.T = T - A [i]
   c.S = S - B [i]

而已!易于在任何编程语言或电子表格中实现.

解决方案是最佳的,因为生成的数组元素永远不会超过理想的非舍入值.让我们用你的例子证明:
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] =圆(A [5]/T*S)= 2.(理想情况下,1.666 ......)
T = 21,S = 10.B [6] =圆形(A [6]/T*S)= 1.(理想情况下,1.666 ......)
T = 18,S = 9. B [7] = round(A [7]/T*S)= 9.(理想情况下,10)

请注意,将B中的每个值与括号中的理想值进行比较,差异不会超过1.

还有一点值得注意的是,重新排列数组中的元素会导致结果数组中出现不同的对应值.我发现按升序排列元素是最好的,因为它导致实际和理想之间的平均百分比差异最小.