RedPackage

red package distribute algorithm in wechat

红包序列限制条件

1. 每个红包至少有1分钱
2. 全部红包总额是总金额数
3. 每个红包的数学期望相等

实现基本思路

假设红包金额为money,拆分为n个红包

• 方法一：平均分布。采用平均分布的方法，将红包中每一分钱等概率分配给每个红包，该红包算法保证每个红包的数学期望为money/n

1. 检验红包金额是否能够发给n个用户
2. 预留n*0.01元钱，保证每个红包至少有1分钱，剩余(money-n*0.01)元钱，即(100*money-n)分钱。采用随机数rand(n)将每一分钱随机分配给长度为n的红包序列。 此处时间复杂度为o(money*100)

• 方法二：正态分布。生成一个红包正态序列。 采用Java自带的Random.nextGaussian()生成一个正态序列，设置正态分布数学期望为(money-n*0.01)/n，标准差为(money-n*0.01)/(n*2)

1. 生成n-1个满足正态分布的红包份额
2. 将剩余的金额放置在最后一个红包

测试用例

方法一：
usecase1: money=10.00, n=5
[2.08,2.04,1.91,2.00,1.91]
[1.94,1.78,2.19,1.96,2.07]
[2.06,1.98,2.00,2.08,1.82]

usecase2: money=5.00, n=10
[0.40,0.42,0.43,0.60,0.53,0.46,0.53,0.57,0.42,0.54]
[0.59,0.37,0.47,0.55,0.52,0.49,0.44,0.48,0.55,0.44]
[0.54,0.48,0.48,0.53,0.48,0.53,0.43,0.53,0.44,0.46]

方法二：
usecase1: money=10.00, n=5
[1.32,3.08,0.80,1.20,3.60]
[1.01,0.82,2.10,2.04,4.03]
[0.05,1.55,4.12,0.01,4.27]

usecase2: money=5.00, n=10
[0.36,0.68,0.35,0.40,0.33,0.59,0.37,0.01,0.65,1.27]
[0.14,0.76,0.40,0.43,0.45,0.69,0.48,0.52,0.39,0.73]
[0.01,0.50,0.03,0.62,0.17,0.70,0.55,0.61,0.49,1.32]

结论

通过分析两种方法得到的红包序列可知：

• 平均分布的每一份红包金额接近平均值，各个红包的金额差距较少。
• 正态分布的每一份红包金额差距较大，更具有可玩性。