考虑下面四个百分比,用浮点数表示:

    13.626332%
    47.989636%
     9.596008%
    28.788024%
   -----------
   100.000000%

我需要用整数表示这些百分比。如果我简单地使用Math.round(),我最终得到的总数是101%。

14 + 48 + 10 + 29 = 101

如果我使用parseInt(),我最终得到了97%。

13 + 47 + 9 + 28 = 97

有什么好的算法可以将任何百分比数表示为整数,同时还保持总数为100%?


编辑:在阅读了一些评论和回答后,显然有很多方法可以解决这个问题。

在我看来,为了保持数字的真实性,“正确”的结果是最小化总体误差的结果,定义为相对于实际值会引入多少误差舍入:

        value  rounded     error               decision
   ----------------------------------------------------
    13.626332       14      2.7%          round up (14)
    47.989636       48      0.0%          round up (48)
     9.596008       10      4.0%    don't round up  (9)
    28.788024       29      2.7%          round up (29)

在平局的情况下(3.33,3.33,3.33)可以做出任意的决定(例如3,4,3)。


当前回答

因为这里没有一个答案似乎能正确解决这个问题,下面是我使用下划线的半模糊版本:

function foo(l, target) {
    var off = target - _.reduce(l, function(acc, x) { return acc + Math.round(x) }, 0);
    return _.chain(l).
            sortBy(function(x) { return Math.round(x) - x }).
            map(function(x, i) { return Math.round(x) + (off > i) - (i >= (l.length + off)) }).
            value();
}

foo([13.626332, 47.989636, 9.596008, 28.788024], 100) // => [48, 29, 14, 9]
foo([16.666, 16.666, 16.666, 16.666, 16.666, 16.666], 100) // => [17, 17, 17, 17, 16, 16]
foo([33.333, 33.333, 33.333], 100) // => [34, 33, 33]
foo([33.3, 33.3, 33.3, 0.1], 100) // => [34, 33, 33, 0]

其他回答

舍入的目标是产生最少的错误。当您对单个值进行舍入时,这个过程简单而直接,大多数人都很容易理解。当你同时四舍五入多个数字时,这个过程变得更加棘手——你必须定义如何组合错误,即必须最小化的错误。

Varun Vohra的答案将绝对误差的总和最小化,而且实现起来非常简单。然而,有一些边缘情况它不能处理-舍入24.25,23.25,27.25,25.25的结果应该是什么?其中一个需要被围捕,而不是减少。你可能会任意选择列表中的第一个或最后一个。

也许用相对误差比绝对误差更好。将23.25四舍五入到24会使它变化3.2%,而将27.25四舍五入到28只会使它变化2.8%。现在有一个明显的赢家。

我们还可以做进一步的调整。一种常见的技术是对每个错误进行平方运算,这样大错误的计数就不成比例地多于小错误。我还会使用非线性除数来得到相对误差——1%的误差比99%的误差重要99倍,这似乎是不对的。在下面的代码中,我使用了平方根。

完整算法如下:

将这些百分比四舍五入后相加,再减去100。这将告诉您这些百分比中有多少必须四舍五入。 为每个百分比生成两个错误分数,一个是四舍五入,另一个是四舍五入。取两者之差。 对上面产生的误差差异进行排序。 对于需要四舍五入的百分比数,从已排序的列表中选取一项,并将四舍五入后的百分比增加1。

您仍然可能有多个具有相同错误和的组合,例如33.3333333,33.3333333,33.3333333。这是不可避免的,结果完全是任意的。下面给出的代码倾向于四舍五入左边的值。

在Python中把它们放在一起是这样的。

from math import isclose, sqrt

def error_gen(actual, rounded):
    divisor = sqrt(1.0 if actual < 1.0 else actual)
    return abs(rounded - actual) ** 2 / divisor

def round_to_100(percents):
    if not isclose(sum(percents), 100):
        raise ValueError
    n = len(percents)
    rounded = [int(x) for x in percents]
    up_count = 100 - sum(rounded)
    errors = [(error_gen(percents[i], rounded[i] + 1) - error_gen(percents[i], rounded[i]), i) for i in range(n)]
    rank = sorted(errors)
    for i in range(up_count):
        rounded[rank[i][1]] += 1
    return rounded

>>> round_to_100([13.626332, 47.989636, 9.596008, 28.788024])
[14, 48, 9, 29]
>>> round_to_100([33.3333333, 33.3333333, 33.3333333])
[34, 33, 33]
>>> round_to_100([24.25, 23.25, 27.25, 25.25])
[24, 23, 28, 25]
>>> round_to_100([1.25, 2.25, 3.25, 4.25, 89.0])
[1, 2, 3, 4, 90]

正如您在最后一个示例中看到的,该算法仍然能够提供非直观的结果。尽管89.0不需要四舍五入,但是列表中的一个值需要四舍五入;相对误差最小的结果是将较大的值舍入,而不是较小的可选值。

这个答案最初主张遍历所有可能的向上舍入/向下舍入组合,但正如评论中指出的那样,更简单的方法效果更好。算法和代码反映了这种简化。

对于那些在熊猫系列中有百分比的人,这里是我的最大余数方法的实现(就像Varun Vohra的答案一样),在那里你甚至可以选择你想要四舍五入的小数。

import numpy as np

def largestRemainderMethod(pd_series, decimals=1):

    floor_series = ((10**decimals * pd_series).astype(np.int)).apply(np.floor)
    diff = 100 * (10**decimals) - floor_series.sum().astype(np.int)
    series_decimals = pd_series - floor_series / (10**decimals)
    series_sorted_by_decimals = series_decimals.sort_values(ascending=False)

    for i in range(0, len(series_sorted_by_decimals)):
        if i < diff:
            series_sorted_by_decimals.iloc[[i]] = 1
        else:
            series_sorted_by_decimals.iloc[[i]] = 0

    out_series = ((floor_series + series_sorted_by_decimals) / (10**decimals)).sort_values(ascending=False)

    return out_series

我认为以下几点可以达到你的目的

function func( orig, target ) {

    var i = orig.length, j = 0, total = 0, change, newVals = [], next, factor1, factor2, len = orig.length, marginOfErrors = [];

    // map original values to new array
    while( i-- ) {
        total += newVals[i] = Math.round( orig[i] );
    }

    change = total < target ? 1 : -1;

    while( total !== target ) {

        // Iterate through values and select the one that once changed will introduce
        // the least margin of error in terms of itself. e.g. Incrementing 10 by 1
        // would mean an error of 10% in relation to the value itself.
        for( i = 0; i < len; i++ ) {

            next = i === len - 1 ? 0 : i + 1;

            factor2 = errorFactor( orig[next], newVals[next] + change );
            factor1 = errorFactor( orig[i], newVals[i] + change );

            if(  factor1 > factor2 ) {
                j = next; 
            }
        }

        newVals[j] += change;
        total += change;
    }


    for( i = 0; i < len; i++ ) { marginOfErrors[i] = newVals[i] && Math.abs( orig[i] - newVals[i] ) / orig[i]; }

    // Math.round() causes some problems as it is difficult to know at the beginning
    // whether numbers should have been rounded up or down to reduce total margin of error. 
    // This section of code increments and decrements values by 1 to find the number
    // combination with least margin of error.
    for( i = 0; i < len; i++ ) {
        for( j = 0; j < len; j++ ) {
            if( j === i ) continue;

            var roundUpFactor = errorFactor( orig[i], newVals[i] + 1)  + errorFactor( orig[j], newVals[j] - 1 );
            var roundDownFactor = errorFactor( orig[i], newVals[i] - 1) + errorFactor( orig[j], newVals[j] + 1 );
            var sumMargin = marginOfErrors[i] + marginOfErrors[j];

            if( roundUpFactor < sumMargin) { 
                newVals[i] = newVals[i] + 1;
                newVals[j] = newVals[j] - 1;
                marginOfErrors[i] = newVals[i] && Math.abs( orig[i] - newVals[i] ) / orig[i];
                marginOfErrors[j] = newVals[j] && Math.abs( orig[j] - newVals[j] ) / orig[j];
            }

            if( roundDownFactor < sumMargin ) { 
                newVals[i] = newVals[i] - 1;
                newVals[j] = newVals[j] + 1;
                marginOfErrors[i] = newVals[i] && Math.abs( orig[i] - newVals[i] ) / orig[i];
                marginOfErrors[j] = newVals[j] && Math.abs( orig[j] - newVals[j] ) / orig[j];
            }

        }
    }

    function errorFactor( oldNum, newNum ) {
        return Math.abs( oldNum - newNum ) / oldNum;
    }

    return newVals;
}


func([16.666, 16.666, 16.666, 16.666, 16.666, 16.666], 100); // => [16, 16, 17, 17, 17, 17]
func([33.333, 33.333, 33.333], 100); // => [34, 33, 33]
func([33.3, 33.3, 33.3, 0.1], 100); // => [34, 33, 33, 0] 
func([13.25, 47.25, 11.25, 28.25], 100 ); // => [13, 48, 11, 28]
func( [25.5, 25.5, 25.5, 23.5], 100 ); // => [25, 25, 26, 24]

最后一件事,我使用问题中最初给出的数字运行函数,与期望的输出进行比较

func([13.626332, 47.989636, 9.596008, 28.788024], 100); // => [48, 29, 13, 10]

这与问题想要的不同=>[48,29,14,9]。我无法理解这一点,直到我看了总误差范围

-------------------------------------------------
| original  | question | % diff | mine | % diff |
-------------------------------------------------
| 13.626332 | 14       | 2.74%  | 13   | 4.5%   |
| 47.989636 | 48       | 0.02%  | 48   | 0.02%  |
| 9.596008  | 9        | 6.2%   | 10   | 4.2%   |
| 28.788024 | 29       | 0.7%   | 29   | 0.7%   |
-------------------------------------------------
| Totals    | 100      | 9.66%  | 100  | 9.43%  |
-------------------------------------------------

从本质上讲,我的函数的结果实际上引入了最少的误差。

小提琴在这里

我曾经写过一个un舍入工具,来找到一组数字的最小扰动来匹配一个目标。这是一个不同的问题,但理论上可以在这里使用类似的想法。在这种情况下,我们有一系列的选择。

因此,对于第一个元素,我们可以四舍五入到14,也可以四舍五入到13。这样做的代价(在二进制整数编程的意义上)对于向上舍入比向下舍入要小,因为向下舍入需要我们将该值移动更大的距离。同样,我们可以把每个数字四舍五入,所以我们总共有16个选择。

  13.626332
  47.989636
   9.596008
+ 28.788024
-----------
 100.000000

我通常会在MATLAB中使用bintprog(一种二进制整数编程工具)解决一般问题,但这里只有几个选项需要测试,所以用简单的循环就可以很容易地测试出16个选项中的每一个。例如,假设我们将这个集合四舍五入为:

 Original      Rounded   Absolute error
   13.626           13          0.62633
    47.99           48          0.01036
    9.596           10          0.40399
 + 28.788           29          0.21198
---------------------------------------
  100.000          100          1.25266

总绝对误差为1.25266。它可以通过以下替代舍入来略微减少:

 Original      Rounded   Absolute error
   13.626           14          0.37367
    47.99           48          0.01036
    9.596            9          0.59601
 + 28.788           29          0.21198
---------------------------------------
  100.000          100          1.19202

事实上,这就是绝对误差的最优解。当然,如果有20项,搜索空间的大小将是2^20 = 1048576。对于30或40个术语,这个空间将是相当大的。在这种情况下,您将需要使用能够有效搜索空间的工具,可能使用分支和绑定方案。

我已经实现了Varun Vohra的答案在这里的列表和字典的方法。

import math
import numbers
import operator
import itertools


def round_list_percentages(number_list):
    """
    Takes a list where all values are numbers that add up to 100,
    and rounds them off to integers while still retaining a sum of 100.

    A total value sum that rounds to 100.00 with two decimals is acceptable.
    This ensures that all input where the values are calculated with [fraction]/[total]
    and the sum of all fractions equal the total, should pass.
    """
    # Check input
    if not all(isinstance(i, numbers.Number) for i in number_list):
        raise ValueError('All values of the list must be a number')

    # Generate a key for each value
    key_generator = itertools.count()
    value_dict = {next(key_generator): value for value in number_list}
    return round_dictionary_percentages(value_dict).values()


def round_dictionary_percentages(dictionary):
    """
    Takes a dictionary where all values are numbers that add up to 100,
    and rounds them off to integers while still retaining a sum of 100.

    A total value sum that rounds to 100.00 with two decimals is acceptable.
    This ensures that all input where the values are calculated with [fraction]/[total]
    and the sum of all fractions equal the total, should pass.
    """
    # Check input
    # Only allow numbers
    if not all(isinstance(i, numbers.Number) for i in dictionary.values()):
        raise ValueError('All values of the dictionary must be a number')
    # Make sure the sum is close enough to 100
    # Round value_sum to 2 decimals to avoid floating point representation errors
    value_sum = round(sum(dictionary.values()), 2)
    if not value_sum == 100:
        raise ValueError('The sum of the values must be 100')

    # Initial floored results
    # Does not add up to 100, so we need to add something
    result = {key: int(math.floor(value)) for key, value in dictionary.items()}

    # Remainders for each key
    result_remainders = {key: value % 1 for key, value in dictionary.items()}
    # Keys sorted by remainder (biggest first)
    sorted_keys = [key for key, value in sorted(result_remainders.items(), key=operator.itemgetter(1), reverse=True)]

    # Otherwise add missing values up to 100
    # One cycle is enough, since flooring removes a max value of < 1 per item,
    # i.e. this loop should always break before going through the whole list
    for key in sorted_keys:
        if sum(result.values()) == 100:
            break
        result[key] += 1

    # Return
    return result