三年前微信红包爆火的时候, 脑补了下背后的分配原理, 并用 C 写了个 demo, 如今回想觉得当时的解法有一定的趣味性, 遂丰富完整了下, 用 js 重写了一遍.
红包算法需满足的规则如下:
所有人抢到金额之和等于红包金额, 不能超过, 也不能少于;
所有人抢到金额的几率相等;
每个人抢到的金额均大于 0.
我脑补的第一画面就是:
排排坐, 分果果
.
于是分配原理如下:
众人们先按抢红包的顺序依次入座, 围成圆环, 将金额均分到每个人, 然后
每人同时将自己手中的金额随机抽出部分给左右临近的 2 个人, 但保证手头至少剩余 1 单位的金额
, 完成分配.
由于在总金额的基础上进行交换分配, 故满足规则一;
由于在金额均分的基础上再进行同等条件的随机金额交换, 故满足规则二;
由于随机分配中保证了至少保留 1 单位的金额, 故满足规则三.
接下来开始实现上述过程
获取分配总额
由于弱类型语言可变换莫测的入参, 在拿到总金额数字的时候必须抖个机灵做下过滤, 这里使用了 jonschlinkert 大神写的 https://github.com/jonschlinkert/is-number 函数, 用于判断入参是否是数字, 否则置它为 0; 另外, 为了规避 js 中小数运算的精度问题, 该算法中只使用整数进行加减, 即将小数放到位整数 (乘倍数), 运算后再缩小回原来倍数 (除倍数).
- class RandomSplit{
- constructor(num){
- // 实际总数
- this.num = this.getNum(num);
- // 放大倍数
- try{
- this.multiple = this.num.toString().split('.')[1].length;
- }catch(e){
- this.multiple = 0;
- }
- // 用于整数运算的总数
- this.calcNum = this.num * Math.pow(10, this.multiple);
- }
- // 判断是否为 number(取用至 "is-number")
- isNumber(num){
- let number = +num;
- if((number - number) !== 0){
- return false;
- }
- if(number === num){
- return true;
- }
- if(typeof num === 'string'){
- if(number === 0 && num.trim() === ''){
- return false;
- }
- return true;
- }
- return false;
- }
- // 获取数字
- getNum(num, defaultNum = 0){
- return this.isNumber(num) ? (+num) : defaultNum;
- }
- }
环形入座, 将总数按份数均分
看 "环形" 二字, 仿佛需要使用双向循环链表, 为节省代码, 这里只用一维数组模拟其效果, 在数组首尾做数据衔接即可. 在该算法中, 所有用于分配交换的数字的原子单位都是整数 1, 所以均分也需要均分为整数, 例如总数
15
均分为
6
份, 先每份分到 2(Math.floor(15/6)===2), 还余
3
(15%6===3), 为了使后面用于计算的概率尽可能平均, 我们需要把这余下的
3
个单位均匀洒落到那 6 份里面, 类似过程如下图:
同理, 若想要均分地更加精确, 可提供精度的位数, 然后将总数按该位数放大, 整数均分后每份再按该精度位数缩小.
于是均分函数如下:
- // 均分份数, 均分精度, 是否直接返回放大后的整数
- average(n, precision, isInt){
- precision = Math.floor(this.getNum(precision, 0));
- n = Math.floor(this.getNum(n));
- let calcNum = this.calcNum * Math.pow(10, precision<0 ? 0 : precision);
- // 份数超过放大后的计算总数, 即不够分的情况
- if(n> calcNum){
- return [];
- }else{
- let index = 0;
- // 平均数
- let avg = Math.floor(calcNum / n);
- // 剩余数
- let rest = calcNum % n;
- // 剩余数填充间隔
- let gap = Math.round((n-rest) / rest) + 1;
- // 原始平均数组
- let result = Array(n).fill(avg);
- //
- while (rest> 0) {
- index = (--rest) * gap;
- result[index>=n ?(n-1) : index]++;
- }
- // 返回放大后的结果数组
- if(isInt){
- return result;
- }
- // 返回处理完符合精度要求的结果数组
- return result.map((item) => {
- return (item / Math.pow(10, this.multiple + precision));
- });
- }
- }
测试效果如下:
相邻随机交换
得到均分数额后, 每个位置先随机出将要给出的数额, 该数额大于等于 0 且小于自己的初始数额, 再将该数额随机划分为两份, 分别给到相邻的左右位置.
- // 随机划分的份数, 划分精度
- split(n, precision){
- n = Math.floor(this.getNum(n));
- precision = Math.floor(this.getNum(precision, 0));
- // 均分
- let arr = this.average(n, precision, true);
- let arrResult = arr.concat();
- for (let i = 0; i <arr.length; i++) {
- // 给出的总额
- let num = Math.floor(Math.random() * arr[i]);
- // 给左邻的数额
- let numLeft = Math.floor(Math.random() * num);
- // 给右邻的数额
- let numRight = num - numLeft;
- // 首尾 index 处理
- let iLeft = i===0 ? (arr.length-1) : (i-1);
- let iRight = i===(arr.length-1) ? 0 : (i+1);
- arrResult[i] -= num;
- arrResult[iLeft] += numLeft;
- arrResult[iRight] += numRight;
- }
- // 缩小至原尺度
- return arrResult.map((item) => {
- return (item / Math.pow(10, this.multiple + precision));
- });
- }
测试效果如下:
整体结果测试
使用 Echarts http://echarts.baidu.com/ 绘制随机分配结果, 将 100 数额划分为 10 份, 精度为 1, 横坐标为顺序位置, 纵坐标为分配到的数额:
那每个位置获得数额的概率是否相等呢? 下图是随机分配 100 次的结果, 并将每个位置的在这 100 次分配中所得的平均数用红色标出:
那分配 1000 次呢?
由此可见, 随机分配次数越多, 每个顺序位置得到的平均数额会稳定在平均分配的数额左右, 公平性得到了印证; 同时, 因为每个位置只能得到相邻两个位置的数额交换, 所以分配结果中任意位置的数额不会超过平均数额的 3 倍 (即自己一毛不拔, 同时又得到相邻者的倾力相助), 这样便可以控制随机分配结果中的最高金额不至于过高.
脑洞来了, 要是并不是左右相邻进行交换呢? 改变交换规则会怎样?
和除自己外的随机位置的两位进行随机数额交换?
从概率上讲, 和之前等价...
只和自己左右或者右边的位置进行随机数额交换?
分配结果依然公平, 但最高数额不会超过平均数额的 2 倍
每个位置随机左右一边然后进行随机数额交换?
又双叒随机, 还是公平的, 最高数额还是少于平均数额的 3 倍 (感觉貌似可以替代之前的方案, 还能顺便降一倍的线性复杂度, 我文章要重写了?! (° °))
谁说只能挑 2 个进行交换? 3 个 4 个 5 个一起来行不行?
行... 挑选位置公平的话, 分配结果就公平, 但是最大数额与交换数量正相关, 但越高的数额, 能得到的概率会急剧减小.
打住打住, 再细想下去, 我的坑怕是要填不完了 _(:з)_
那这个东西除了可以分红包还能干嘛?
我用它写过一个没有后端数据的进度条, 一抖一抖增加长短不一还仿佛真的在帮你加载一样...
其他... 望君发挥想象力
最后 ( ˙-˙ )
来源: https://juejin.im/post/5ae413946fb9a07a9c03f7f7