最大余额法

2021/09/17

算法

最大余额法

起因

最近刚好在和同事这么计算一组数值的百分比，谈论到单纯的计算出百分比，然后相加，经常会出现结果不是刚好等于100%的情况。然后我就说出了我比较粗暴的解决方法，就是最后一个百分数直接通过100%减去前面的计算出的百分比总和得出，这样就可以保证100%了。然后想到了Echarts也是有类似的计算百分比的功能的。就好奇Echarts是怎么实现的，就研究了一下，发现它是通过最大余额法实现的。

定义

最大余额方法（英语：largest remainder method）又称数额制，是比例代表制投票制度下，一种议席分配的方法，相对于最高均数方法。

透过最大余额方法，候选人须以名单参选，每份名单的人数最多可达至相关选区内的议席数目。候选人在名单内按优先次序排列。选民投票给一份名单，而不是个别候选人。投票结束后，把有效选票除以数额（见下）。一份名单每取得数额1倍的票数，便能获分配一个议席。每份名单的候选人按原先订立的顺序当选。

当每份名单的余额均比“数额”为低的时候，则依每份名单余额的大小顺序分配剩余议席；最大余额方法因而得名。

数额

最常用的最大余额方法，分别使用4种数额：

黑尔数额：将总有效票数除以议席数目。名称源自英国大律师托马斯·黑尔。在各种数额之中，黑尔数额是历史最悠久、计算最简易、使用最广泛的方法。
特罗普数额：1+总有效票数除以（议席数目+1）。名称源自英国数学家亨利·特罗普。南非国会使用这种方法。
因佩里亚利数额：总有效票数除以（议席数目+2）。厄瓜多尔国会选举是少数采用这种数额的选举，因为得最大余额的名单，未必能取得剩余的议席，因为所有议席有可能都被数额完整分配。
哈根巴赫-比绍夫数额：总有效票数除以（议席数目+1）。名称源自瑞士物理学家兼数学教授爱德华·哈根巴赫-比绍夫。

实现黑尔数额最大余额法

public static decimal GetPercentValue(decimal[] arr, int idx, int precision)
{
    if (arr.Length - 1 < idx)
        return 0;
    // 求和
    var sum = arr.Sum();
    // 10的2次幂是100，用于计算精度。
    var digits = (decimal)Math.Pow(10, precision);
    // 扩大比例100
    var votesPerQuota = new decimal[arr.Length];
    for (var i = 0; i < arr.Length; i++)
    {
        var val = arr[i] / sum * digits * 100;
        votesPerQuota[i] = val;
    }
    // 总数，扩大比例意味着总数也要扩大
    var targetSeats = digits * 100;
    // 再向下取整，组成数组
    var seats = new decimal[arr.Length];
    for (var i = 0; i < votesPerQuota.Length; i++)
    {
        seats[i] = Math.Floor(votesPerQuota[i]);
    } 
    
    // 再新计算合计，用于判断与总数量是否相同,相同则占比会100%
    var currentSum = seats.Sum();
    // 余数部分的数组:原先数组减去向下取值的数组,得到余数部分的数组
    var remainder = new decimal[arr.Length];
    for (var i = 0; i < seats.Length; i++)
    {
        remainder[i] = votesPerQuota[i] - seats[i];
    }
    while (currentSum < targetSeats)
    {
        decimal max = 0;
        var maxId = 0;
        for (var i = 0; i < remainder.Length; ++i)
        {
            if (remainder[i] <= max) continue;
            max = remainder[i];
            maxId = i;
        }
        // 对最大项余额加1
        ++seats[maxId];
        // 已经增加最大余数加1,则下次判断就可以不需要再判断这个余额数。
        remainder[maxId] = 0;
        // 总的也要加1,为了判断是否总数是否相同,跳出循环。
        ++currentSum;
    }
    return seats[idx] / digits;
}

Atan方法

用于返回正切值的指定数字的角度

1 2	double d = 0.75; double m = Math.Atan(d);

Pow方法

用于返回指定数字的指定次幂

1	double d = Match.Pow(2,3);//表示2的3次幂

Round方法

用于将值舍入到最接近的整数或指定的小数位数

//将小数值舍入最接近的整数
double d = Math.Round(2.44);//decimal/double
//将小数值舍入到指定精度
d = Math.Round(2.44,2);//decimal/double,int
//将小数值舍入最接近的整数
d = Math.Round(2.44,MidpointRounding.ToEven);//ToEven 舍入最接近的偶数;AwayFromZero 舍入绝对值较小的值
d = Math.Round(2.44,2,MidpointRounding.ToEven);

利弊

使用黑尔数额的最大余额方法，并不偏重得票率较多或较少的名单，好处在于能给出中立、但同时具广泛代表性的选举结果。

算法