红包分发 - 二倍均值随机算法

简介

蒙特卡罗方法的核心思想主要在于构造一个数学模型，并基于若干个随机变量和统计分析的方法求出若干个估计值（随机数），在某种程度上并不适用于抢红包系统生成随机金额的几率相等、随机金额之和等于总金额等要求。 然而我们却可以借助其构造数学模型的思想，将总金额M和总个数N作为模型变量，从而求得一组红包随机金额。

当用户发出固定总金额为M、红包个数为N的红包后，由于系统后端采用的是预生成方式，因而将在后端生成N个随机金额的小红包并存储至缓存中，等待着被抢。 小红包随机金额的产生对用户而言是透明的，用户也无须知晓红包随机金额的产生原理与规则， 因而对于抢红包系统来说，只需要保证系统后端每次对于总金额M和红包个数N生成的小红包金额是随机且平等的，即间接性地保证每个用户抢到的红包金额是随机产生且概率是平等的即可。

需求背景

发放红包需满足以下条件:

• 公平性：每个人参与抢红包的用户抢到红包金额时，几率是相等的
• 随机性：金额分配不可预测
• 总额约束：所有红包金额之和等于总金额
• 边界控制：每个人至少获得0.01元
• 性能要求：算法需高效，支持高并发

算法原理图解

代码实现

java

/**
* 发红包算法，金额参数以分为单位
* @param totalAmount    红包总金额-单位为分
* @param totalPeopleNum 总人数
* @return
*/
public static List<Integer> divideRedPackage(Integer totalAmount, Integer totalPeopleNum) {
    //用于存储每次产生的小红包随机金额List –金额单位为分
    List<Integer> amountList = new ArrayList<Integer>();
    //判断总金额和总个数参数的合法性
    if (totalAmount > 0 && totalPeopleNum > 0) {
        //记录剩余的总金额-初始化时金额即为红包的总金额
        Integer restAmount = totalAmount;
        //记录剩余的总人数-初始化时即为指定的总人数
        Integer restPeopleNum = totalPeopleNum;
        //定义产生随机数的实例对象
        Random random = new Random();
        //不断循环遍历、迭代更新地产生随机金额，直到N-1>0
        for (int i = 0; i < totalPeopleNum - 1; i++) {
            //随机范围：[1，剩余人均金额的两倍)，左闭右开 -amount即为产生的随机金额R -单位为分
            int amount = random.nextInt(restAmount / restPeopleNum * 2 - 1) + 1;
            //更新剩余的总金额 M = M - R
            restAmount -= amount;
            //更新剩余的总人数N = N - 1
            restPeopleNum--;
            //将产生的随机金额添加进列表List中
            amountList.add(amount);
        }
        //循环完毕，剩余的金额即为最后一个随机金额，也需要将其添加进列表中
        amountList.add(restAmount);
    }
    //将最终产生的随机金额列表返回
    return amountList;
}

javascript

/**
 * 微信红包算法实现
 * @param {number} total - 总金额（元）
 * @param {number} num - 红包数量
 * @return {number[]} - 分配结果数组
 */
function hongbao(total, num) {
  // 转为分计算避免浮点误差
  let restAmount = total * 100;
  let restNum = num;
  const packets = [];
  
  // 前n-1个红包,最后一个红包为剩余的金额，不可随机分配
  for (let i = 0; i < num - 1; i++) {
    // 核心算法：二倍均值法
    const max = Math.floor(restAmount / restNum * 2);
    //Math.floor 向下取整，确保结果为整数（避免出现小数金额）
    const amount = Math.floor(Math.random() * max) + 1; // 至少1分钱
    
    restAmount -= amount;
    restNum--;
    packets.push(amount);
  }
  
  // 最后一个红包
  packets.push(restAmount);
  
  // 转换回元，保留两位小数
  return packets.map(amount => (amount / 100).toFixed(2));
}