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

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

有一个很简单的回答了这个问题：我已经做了很多次。在每次分配到新阵列后，您将减少您使用的值，如下所示：

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]

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

该解决方案是最佳的，因为结果数组的元素永远不会超过其理想的非四舍五入值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 = （4）/ T * S）= 2。（理想地，1.666 ...）
T = 27，S = （理想情况下，1.666 ...）
T = 21，S = 10。B [6] = round（A [6]/T * S）= 1.（理想情况下，1.666 ....）
T = 18，S = 9   B [7] = （A [7]/T * S）= 9（理想情况下为10）

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

注意到重新排列数组中的元素可能会导致结果数组中的不同对应值也很有趣。我发现按照升序排列元素是最好的，因为它导致实际和理想之间的最小平均差异为百分比。

Answer 2

不表现良好，但会提供正确的结果幼稚的溶液...

编写给定的阵列具有八个整数（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)]++ 

Answer 3

您已设置3个不兼容的要求。与[1,1,1]成比例的整数值数组不能与20的和相加。您必须选择“总和为20”，“与输入成比例”和“整数值”要求中的一个。

如果您选择打破整数值的要求，则使用浮点数或有理数。如果你选择打破确切的总和要求，那么你已经解决了这个问题。选择打破比例是有点棘手的。你可能采取的一种方法是找出你的总和有多远，然后通过输出数组随机分配纠正。例如，如果你输入的是：

[1, 1, 1] 

，那么你可以先让它总结以及可能的，同时仍然比例：

[7, 7, 7] 

，自20 - (7+7+7) = -1，选择一个元素随机递减：

[7, 6, 7] 

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

Answer 4

所以上面的答案和评论是有帮助的......特别是来自@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 

（我补充说，如果累加器>余，我增加前一个值，而不是当前值的增强）

Answer 5

你的问题是类似的，你想proportional representation在你的案例中[3，3，3，3，3，3，18]共享N个席位（在你的案例20中）与所有投票成员之间的份额比例。

有几种方法可用于不同的国家处理舍入问题。下面My code使用在瑞士，所使用的方法Hagenbach-Bischoff quota基本上由分配（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]