無尾差分贓法崩壞記

自從經前輩醍糊灌頂，學會"未分配數量 * (權重 / 尚未分配權重總和)"一次到位的無尾差分贓演算法後，開心地用了好幾年，後來更演化出LINQ進化版，從此在.NET中要分贓算錢如虎添翼! 幾年下來，未曾得接獲於此演算法的缺點回饋，於是它在我心中一直維持完美無瑕的女神形象!

直到最近一個極端例子讓我的女神當場崩壞，猶如無意瞥見林志玲摳腳挖鼻孔般讓人心碎與震撼~~

用一個例子重現問題:

巴菲特跟10個散戶合資買基金，散戶每人出100元，巴菲特出資100萬，基金單位淨值9.5元，最小單位為1，求巴菲特與散戶各分得多少單位。

為了應用LINQ式PerfectDivide()計算，此場需宣告一個簡單的Data物件，用以記載金額、單位數、分配單位數等資訊。

using System;

public class Data

{

    public Data(decimal amt, decimal prz)

    {

        Amt = amt;

        Prz = prz;

        //計算單位數 = 金額除單價取整數

        CalcQty = Math.Round(Amt / Prz, MidpointRounding.AwayFromZero);

    }

    public decimal Amt; //金額

    public decimal Prz; //單價

    public decimal CalcQty; //計算單位數(等於金額除單價取整數)

    //單位數取整數時產生的四捨五入差額

    public decimal CalcDiff { get { return CalcQty - Amt / Prz; } }

    public decimal DistQty; //分配單位數

    //計算單位數與分配單位數間的

    public decimal DistDiff { get { return DistQty - CalcQty; } }

}

接著用一小段程式建立List<Data>，放入10筆散戶的100元，再放入巴菲特的100萬。先計算100萬1000元可買105,368單位，再使用PerfectDivide將105,368單位依o.Amt權重分配給巴菲特及散戶。

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.IO;

namespace Test1

{

    class Program

    {

        static void Main(string[] args)

        {

            decimal prz = 9.5M;

            var pool = new List<Data>();

            //放入10筆100元

            for (int i = 0; i < 10; i++)

                pool.Add(new Data(3000, prz));

            //最後放入1筆100萬元

            pool.Add(new Data(1000000, prz));

            //先算出Amt總額

            var totalAmt = pool.Sum(o => o.Amt);

            //計算總額可購買數量

            var totalQty = Math.Round(totalAmt / prz, MidpointRounding.AwayFromZero);

            //進行無尾差分贓

            pool.PerfectDivide(totalQty, 0, o => o.Amt, (o, v) => { o.DistQty = v; });

            //Dump結果

            decimal totalDiff = 0;

            foreach (var o in pool)

            {

                //累計差額

                totalDiff += o.CalcDiff + o.DistDiff;

                //列印結果

                Console.WriteLine("{0}\t{1:N4}\t{2}\t{3:N4}\t{4}\t{5}\t{6:N4}", 

                    o.Amt, o.Amt / o.Prz, o.CalcQty, o.CalcDiff, 

                    o.DistQty, o.DistDiff, totalDiff);

            }

            Console.Read();

        }

    }

}

沒想到，計算結果讓巴菲特氣到翻桌!

100     10.5263 11      0.4737  11      0       0.4737
100     10.5263 11      0.4737  11      0       0.9474
100     10.5263 11      0.4737  11      0       1.4211
100     10.5263 11      0.4737  11      0       1.8947
100     10.5263 11      0.4737  11      0       2.3684
100     10.5263 11      0.4737  11      0       2.8421
100     10.5263 11      0.4737  11      0       3.3158
100     10.5263 11      0.4737  11      0       3.7895
100     10.5263 11      0.4737  11      0       4.2632
100     10.5263 11      0.4737  11      0       4.7368
1000000 105,263.1579    105263  -0.1579 105258  -5      -0.4211

10名散戶的100元/9.5=10.5263，四捨五入後為11單位，分配結果10名散戶都拿到11單位，而中間產生的尾差-4.7368單位由出資100萬的巴菲特先生吸收，因此按計算應拿105,263單位卻只能分到105,258單位，足足少了5個單位，如果你是巴菲特，此刻也會想找到算錢的人，把他的頭扭下來吧? 暗陰羊，出錢最多的人，還要負責吞下所有人的尾差!!

雖然5/105,263 < 0.004%，但取整數時尾差大於+1或小於-1本身是不合理的，即使差額所佔比例再小，任何一個人的帳面產生超過正負一個最小單位的結果，也很難為人所接受致。而分析這個問題的根源:

以上演算法取得分配數量的原理為"某筆資料的分配單位數 = 尚未分配單位數 * (某筆資料金額 / 所有尚未分配資料的金額總和)"，當未分配資料中有一筆無敵大，其餘都是小金額時，分配比率會變成 SmallMoney / (SmallMoney * N + BigMoney)，但因為SmallMoney *N與BigMoney相比猶如九牛一毛，故SmallMoney * N + BigMoney約等於BigMoney，因此每一筆的分配比率幾乎都是SmallMoney / BigMoney，造成了每一筆小金額的分配比例均相等的結果。

而無尾差分配之所以能把尾差隨機地平均分配在多筆，靠的是逐筆計算分配比例時會產生微小變化，而變化過程中會隨機越過四捨五入門檻，產生進位或捨去的不同結果。一旦分配比例固定不動，微小變化消失，隨機產生進位捨去效果也隨之消失。  

因此，只要能避免 (某筆資料金額 / 所有尚未分配資料的金額總和) 一直逼近固定值的情境，就能防止上述情況發生。而分配比例維持固定值的狀況，主要會發生在”尚未分配資料的金額總和存在超大金額，嚴重壓抑其他金額對分配比例之影響”的情境!

追加一個實驗，證明當100萬位於第一筆時，便不會發生獨吞尾差的狀況:

1000000 105,263.1579    105263  -0.1579 105263  0       -0.1579
100     10.5263 11      0.4737  11      0       0.3158
100     10.5263 11      0.4737  10      -1      -0.2105
100     10.5263 11      0.4737  11      0       0.2632
100     10.5263 11      0.4737  10      -1      -0.2632
100     10.5263 11      0.4737  11      0       0.2105
100     10.5263 11      0.4737  10      -1      -0.3158
100     10.5263 11      0.4737  11      0       0.1579
100     10.5263 11      0.4737  10      -1      -0.3684
100     10.5263 11      0.4737  11      0       0.1053
100     10.5263 11      0.4737  10      -1      -0.4211

由此推論，只要盡早將超大金額的資料分配掉，盡速將其由”尚未分配資料的金額總和”中移除，就能避開分配比例固定現象解決問題，而在分配前，先將金額由大至小排序，是及早將大金額自總和中移除的有效做法。而由心理面解釋，最早被分配的人不會有分配差異，金額比重高的人貢獻度大，講話大聲，享受不跟大家一起平均承擔尾差的特權，也稱得上合情合理! 因此，無尾差分贓演算法還要加上一道程序，先將資料依權重由大至小排序再進行分配，才能避免在極端案例下出現瑕疵。

至於PerfectiveDivide()，需要補上一行，將IEnumerable<T>重新用權重(剛好可以直接借用getWeight)由大至小排序，即可避免崩壞，試著把它再推回"Perfect"的偉大航道~~~

        public static IEnumerable<T> PerfectDivide<T>(

            this IEnumerable<T> ienum, decimal amt, int decimals,

            Func<T, decimal> getWeight,

            Action<T, decimal> resultCallback)

        {

            //為避免權重大小懸殊時，超大權重排在後方會造成尾差無法分散

            //進行分配前先依權重由大至小排序

            ienum = ienum.OrderByDescending(getWeight);

            decimal[] weights = ienum.Select(getWeight).ToArray();

            try

            {