佛系红包算法，了解一下？

顶级算法后台回复 1024 有特别礼包

责编：顶级算法 | 来源：youngdro

链接：juejin.im/post/5ae413946fb9a07a9c03f7f7

上一篇精彩：华为首次自曝“天才少年”成果：入职不到一年就干成这件大事，网友：值200万年薪！

大家好，我是顶级算法。

三年前微信红包爆火的时候，脑补了下背后的分配原理，并用C写了个demo，如今回想觉得当时的解法有一定的趣味性，遂丰富完整了下，用js重写了一遍。

红包算法需满足的规则如下：

1. 所有人抢到金额之和等于红包金额，不能超过，也不能少于；

2. 所有人抢到金额的几率相等；

3. 每个人抢到的金额均大于0。

我脑补的第一画面就是：排排坐，分果果。

于是分配原理如下：

众人们先按抢红包的顺序依次入座，围成圆环，将金额均分到每个人，然后每人同时将自己手中的金额随机抽出部分给左右临近的2个人，但保证手头至少剩余1单位的金额,完成分配。

• 由于在总金额的基础上进行交换分配，故满足规则一；

• 由于在金额均分的基础上再进行同等条件的随机金额交换，故满足规则二；

• 由于随机分配中保证了至少保留1单位的金额，故满足规则三。

接下来开始实现上述过程

1、获取分配总额

由于弱类型语言可变换莫测的入参，在拿到总金额数字的时候必须抖个机灵做下过滤，这里使用了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;
 }
}

2、环形入座，将总数按份数均分

看“环形”二字，仿佛需要使用双向循环链表，为节省代码，这里只用一维数组模拟其效果，在数组首尾做数据衔接即可。

在该算法中，所有用于分配交换的数字的原子单位都是整数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));
   });
 }
}

测试效果如下：

3、相邻随机交换

得到均分数额后，每个位置先随机出将要给出的数额，该数额大于等于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绘制随机分配结果，将100数额划分为10份，精度为1，横坐标为顺序位置，纵坐标为分配到的数额：

那每个位置获得数额的概率是否相等呢？下图是随机分配100次的结果，并将每个位置的在这100次分配中所得的平均数用红色标出：

那分配1000次呢？

由此可见，随机分配次数越多，每个顺序位置得到的平均数额会稳定在平均分配的数额左右，公平性得到了印证；同时，因为每个位置只能得到相邻两个位置的数额交换，所以分配结果中任意位置的数额不会超过平均数额的3倍（即自己一毛不拔，同时又得到相邻者的倾力相助），这样便可以控制随机分配结果中的最高金额不至于过高。

脑洞来了，要是并不是左右相邻进行交换呢？改变交换规则会怎样？

• 和除自己外的随机位置的两位进行随机数额交换？从概率上讲，和之前等价...

• 只和自己左右或者右边的位置进行随机数额交换？分配结果依然公平，但最高数额不会超过平均数额的2倍

• 每个位置随机左右一边然后进行随机数额交换？又双叒随机，还是公平的，最高数额还是少于平均数额的3倍（感觉貌似可以替代之前的方案，还能顺便降一倍的线性复杂度，我文章要重写了？！(°ー°〃)）

• 谁说只能挑2个进行交换？3个4个5个一起来行不行？行... 挑选位置公平的话，分配结果就公平，但是最大数额与交换数量正相关，但越高的数额，能得到的概率会急剧减小。

打住打住，再细想下去，我的坑怕是要填不完了 _(:з」∠)_

那这个东西除了可以分红包还能干嘛？

我用它写过一个没有后端数据的进度条，一抖一抖增加长短不一还仿佛真的在帮你加载一样...

其他...望君发挥想象力

最后 ( ˙-˙ )

觉得不错？欢迎转发分享给更多人

公众号后台回复 算法 或者 算法心得 有惊喜礼包！顶级算法交流群

 「顶级算法」建立了读者算法交流群，大家可以添加小编微信进行加群。欢迎有想法、乐于分享的朋友们一起交流学习。

扫描添加好友邀你进算法群，加我时注明【姓名+公司+职位】

版权申明：内容来源网络，版权归原作者所有。如有侵权烦请告知，我们会立即删除并表示歉意。谢谢。

往日分享：

关注顶级算法修炼内功