比例舍入误差

Question

我有一段代码，可以将大数据集转化为比例较小的数据集，我来解释一下：

假设你有20个蓝色弹珠和10个红色弹珠，如果我想用3个弹珠来表示这个数据，我会使用2个蓝色和1个红色。

我不介意结果不是完全准确的，例如用4个弹珠来表示17个蓝色和16个红色。最接近的比例表示方法是使用2个蓝色和2个红色，这样也可以。

以下是我的Python代码:

from random import randrange

data_set = [randrange(100, 1000) for x in range(5)]
required_amount = 20
special_number = required_amount / sum(data_set)
proportional_data_set = [round(x * special_number) for x in data_set]

print(data_set)
print(required_amount)
print(proportional_data_set)
print(sum(proportional_data_set))

问题在于我说需要的样本数是20，但有时比例数据集会给出总数为21或19。我认为这是由于一些舍入误差导致的，但是否有更好的方法来解决这个问题呢？

正确工作的示例输出如下：

[832, 325, 415, 385, 745]
20
[6, 2, 3, 3, 6]
20

一个示例工作不正确的情况如下：

[414, 918, 860, 978, 438]
20
[2, 5, 5, 5, 2]
19

如果有人知道类似的方法也能做到这样，那就太好了。

- ThatOneGuyInXNA

---

可能是相似的问题：为了弥补四舍五入误差，分配一个整数数组。 - tzaman

感谢提供这个资源。虽然它并没有完全回答我的问题。 - ThatOneGuyInXNA

Answer 1

这是解决问题的一种方式。计算 data_set 中每个“大理石”所含的单位数，将其称为 special_number。然后使用 divmod() 函数来计算比例数量和余数。由于 divmod() 返回整数商，因此在大多数情况下，proportional_data_set 的总和会小于 required_amount。

最后，使用循环找到最高余数，并增加 proportional_data_set 直到 sum(proportional_data_set) = required_amount。

from random import randrange

data_set = [randrange(100, 1000) for x in range(5)]
required_amount = 20
special_number = sum(data_set) // required_amount

print("Data set:")
print(data_set)
print("Special number:")
print(special_number)

# divmod() returns a pair of numbers, split them into quotients and remainders
pairs = [divmod(x, special_number) for x in data_set]
proportional_data_set = [x[0] for x in pairs]
remainder = [x[1] for x in pairs]

print
print("Proportional data set before adjusting:")
print(proportional_data_set), "=", sum(proportional_data_set)
print("Remainders:")
print(remainder)

while sum(proportional_data_set) < required_amount:
    i = remainder.index(max(remainder))    # index of the highest remainder
    proportional_data_set[i] += 1          # add another marble to this index
    remainder[i] = -1                      # don't use this remainder again

print
print("Proportional data set after adjusting:")
print(proportional_data_set), "=", sum(proportional_data_set)
print("Remainders:")
print(remainder)

输出结果如下：

Data set:
[546, 895, 257, 226, 975]
Special number:
144

Proportional data set before adjusting:
[3, 6, 1, 1, 6] = 17
Remainders:
[114, 31, 113, 82, 111]

Proportional data set after adjusting:
[4, 6, 2, 1, 7] = 20
Remainders:
[-1, 31, -1, 82, -1]

最高余数用于增加比例数据集，然后设置为-1。

- Brent Washburne

---

谢谢，但是假设比例数据集总和超过所需数量而不是少于它，我认为在调整后这不会减少它。 - ThatOneGuyInXNA

Hagenbach-Bischoff配额法通过最初除以（N+1）来解决这个问题，这保证了只需添加到初始分配即可。我认为这个方法也可以应用相同的原则。 - Simon

比例数据集始于向下舍入的值，其余数为小数部分。比例数据集的总和不可能超过所需数字。也不需要使用（N+1）。 - Brent Washburne

@BrentWashburne：啊，我现在看到了初始的向下舍入。 - Simon

Answer 2

我本想基于输入数据的累积总和和比例输出值的累积总和之间的Bresenham线提供一个解决方案，但 (a) 结果证明它给出了错误的答案 - 见下文 - 和 (b) 我相信 @tzaman指向的为舍入误差比例分配整数数组提供了比我对Bresenham方法所做的任何更正都更简单的解决方案（proportional()函数由@Dr. Goulu提供）：

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

print (proportional(20,[832, 325, 415, 385, 745]))
print (proportional(20,[414, 918, 860, 978, 438]))

... 给出以下输出结果：

[6, 2, 3, 3, 6]
[2, 5, 5, 6, 2]

Bresenham直线算法（非）解决方案

对于那些可能对Bresenham直线算法（非）解决方案感兴趣的人，这里有一个基于这里的代码的解决方案：

import itertools, operator

def bresenhamLine(x0, y0, x1, y1):
    dx = abs(x1 - x0)
    dy = abs(y1 - y0)
    sx = x0 < x1 and 1 or -1
    sy = y0 < y1 and 1 or -1
    err = dx - dy
    points = []
    x, y = x0, y0
    while True:
        points += [(x, y)]
        if x == x1 and y == y1:
            break
        e2 = err * 2
        if e2 > -dy:
            err -= dy
            x += sx
        if e2 < dx:
            err += dx
            y += sy
    return points

def proportional(n,inp):
    cumsum = list(itertools.accumulate(inp))
    pts = bresenhamLine(0,0,max(cumsum),n)
    yval = [y for x,y in pts]
    cumsum2 = [yval[x] for x in cumsum]
    res = [cumsum2[0]]
    for i,x in enumerate(cumsum2[1:]):
        res.append(x-cumsum2[i])
    return res

print (proportional(20,[832, 325, 415, 385, 745]))
print (proportional(20,[414, 918, 860, 978, 438]))

...然而输出结果是

[6, 3, 3, 2, 6]
[2, 5, 5, 6, 2]

...这是不正确的，因为对于第一个列表中的第二到第四项，它将“2”分配给中间排名的项目而不是最低排名的项目。Hagenbach-Bischoff配额方法可以正确地进行分配。

- Simon