2021年部门线上年会红包随机生成算法详解
文章目录
一、前言
由于疫情影响，2021年该部门将通过微信小程序进行线上直播。为了活跃年会气氛，年会直播间将举办抢红包环节。由于产品要求，红包金额必须是随机生成的，所以这就涉及到当指定了红包的总金额、数量以及最大最小值时，如何生成红包金额。
可以看到，生成随机红包数量的输入是一个四元组，其中sum是红包总数，num是红包数量，min和max是最小值和最大值分别是红包。所以这可以抽象为以下算法：
input: output: 随机红包金额数组
因为法定货币有最小单位，例如人民币是分，所以上面输入的四元组可以看成整数。
2.参考微信群红包算法
本质上，这和微信群红包没有什么区别。发放固定总额的红包，并指定红包数量。那么随机分配红包数量需要满足哪些规则呢？
（1）大家抢到的金额总和等于红包总金额，不能多也不能少。
（2）抢到的红包金额至少为一分钱。
（3）确保抢红包的人收到的红包金额是随机的。
之前看过微信群红包金额分发的实现代码。
微信群红包最低为1分钱，最高为剩余红包平均金额的2倍。为什么是这两个值呢？因为这样做会保证随机值的期望值等于均值，保证不会因为抢红包的顺序而造成混乱。造成不公平。这两个值是内置于算法中的，不提供给用户指定。另外，总金额sum和数量num由用户指定。
微信群红包为什么有上限？因为如果没有上限，就会出现不公平的现象。即提前领取红包的同学，随机范围较大，领取大红包的几率较高。一旦前面的同学随机得到的金额较大，后面的同学可以随机的范围就逐渐缩小，抢红包就变成了一场手速的游戏。
事实上，微信群红包采用的是双重均值法，即每次的随机上限是剩余红包金额平均值的两倍。
微信群红包金额分配算法如下：
每次抢红包直接随机，随机的范围是[1, 剩余红包金额均值的两倍]，单位分
这个公式保证了每次随机金额的平均值相等，不会因为抢红包的顺序造成不公平。
事实上，微信群红包的算法虽然公平，但却存在缺陷。不过这款微信产品对于学生来说是可以接受的，但是体验上就不是那么人性化了，因为有时候发群红包的时候会出现以下两种情况之一。红包的数额非常大。
造成这种情况的原因是，上述随机上限max是剩余红包平均金额的两倍。如果剩余红包的平均金额越来越大，那么后面抢的越多，期望就越大，就会出现上述情况。当然，这种情况发生的概率很小，要求最后两个之前的所有结果都小于残差均值，这是一个很小的量。
这说明了什么问题？红包金额的随机分配算法不是标准算法，而是产品逻辑。如果你是产品同学，你可以创建一个你想要的随机分配算法。比如随机范围严格在[min,max]之间，或者像微信群红包，max每次抢红包都会动态变化。 。
我们来说说大家最关心的问题，就是如何抢大红包。通过上面的介绍，结论是，除了最后两次红包金额之一外，可能会很大，因为每次都是在[0.01 - 剩余均值*2]之间随机，剩余均值可能会随着时间一分一秒过去，最后两个红包到了。当职位可供争夺时，期望是最高的。如果红包数量足够的话，那么只有最后两个劫匪才有可能拿到大红包。但大多数情况下，人太多了，需要努力去抢红包。这种情况下，你不能保证你就是最后两个抢到红包的人。
3.一个可用的随机算法
这次年会上，产品同学开始告诉我，红包的金额需要像微信群红包一样随机分配。但仔细研究微信群红包算法后，发现产品同学想要的效果和微信群红包不一样。她想要的红包金额在[min,max]范围内严格随机。
实施过程中必须具备以下条件：
（1）大家抢到的金额总和等于红包总金额，不能多也不能少；
（2）抢到的红包金额在[min,max]之间；
（3）确保抢红包的人收到的红包金额是随机的。
下面给出一种可行的随机分配算法。
// min 最小金额分 max 最大金额分 num 红包数量 sum 红包总额分 input： // 参数合法性校验 step 1: min*num <= sum <= max*num step 2: 将 num 个在 min 填入数组 step 3: 循环随机一个范围为 [0, max - min] 数加到最小值数组中。如果随机数大于剩余金额，则取剩余金额作为随机数；如果累加值大于最大值，则取最大值与原值差值作为随机数。如果剩余金额为 0 结束循环 step 4: 如果均值靠近 min 或 max，第三步分别会出现很多 min 或者 max，看起来不够随机。这里需要经过一轮或多轮遍历，将 (min, max) 之间的数减掉部分给到 min 或者从 max 获得部分 step 5: 打乱数组顺序
注意第四步是按一定比例消除最小值或最大值还是完全消除也是产品逻辑，需要产品同学来决定。以下实现示例仅执行一个周期，并且可能具有少量的最小值或最大值。
下面以实现为例。
// brief: 获取随机整数 [min, max] function random(min, max) { const range = max - min; const rand = Math.round(Math.random() * range); return min + rand; } // brief: 消除最小值和最大值 function smooth(min, max, arr) { for (let i = 0; i < arr.length; i++) { if (!(min < arr[i] && arr[i] < max)) { continue } for (let j = 0; j < arr.length; j++) { // 消除最小值 if (arr[j] === min) { let rm = Math.floor((arr[i] - min)/10) arr[i] -= rm arr[j] += rm break } // 消除最大值 if (arr[j] === max) { let rm = Math.floor((max - arr[i])/10) arr[i] += rm arr[j] -= rm break } } } } // brief: 打乱数组顺序 function shuffle(arr) { arr.sort(() => Math.random() - 0.5);
上述代码可以在IDE中执行。
接下来使用两组输入参数，平均值分别接近最小值和最大值，观察多次运行后的输出结果。
第一批入场的最低金额为5元，最高金额为50元，数量为10个，总金额为100元。平均值 10 接近最小值。
// 单位为分 console.log(randnum(500, 5000, 10, 10000)) // 第一轮结果 [ 516, 3317, 646, 515, 677, 636, 1861, 501, 518, 813 ] // 第二轮结果 [ 724, 502, 500, 726, 2761, 2740, 500, 502, 522, 523 ] // 第三轮结果 [ 500, 500, 1009, 899, 504, 4492, 500, 505, 551, 540 ]
第二组输入参数，平均值接近最大值，最小金额为5元，最大金额为50元，数量为10个，总金额为450元。平均值 45 接近最大值。
// 单位为分 console.log(randnum(500, 5000, 10, 40000)) // 第一轮结果 [ 4832, 4999, 4953, 4990, 3515, 3929, 4835, 4572, 3482, 4893 ] // 第二轮结果 [ 4868, 5000, 4901, 5000, 4733, 5000, 4106, 3804, 2588, 5000 ] // 第三轮结果 [ 4999, 3493, 3795, 5000, 3210, 4849, 4867, 4985, 5000, 4802 ]
从上面的实验结果可以看出，相同输入参数的多次运行结果是不同的。如果平均值接近最小值或最大值，则结果可能分别有多个最小值和最大值。通过多次执行该函数可以完全消除这种情况。
参考
漫画：抢红包算法如何实现？
微信幸运红包背后的算法逻辑