RedPaket - 微信红包金额分配算法
jopen
8年前
红包领了不少，据观察红包主要有以下几个限制条件：
- 1.所有人都能分到红包，也就是不会出现红包数值为0的情况。
- 2.所有人的红包数值加起来等于支付的金额。
- 3.红包波动范围比较大，约5%~8%的红包数值在平均值的两倍以上，同时数额0.01出现的概率比较高。
- 4.红包的数值是随机的，并且数值的分布近似于正态分布。
基本思路：
- 1.因为要保证每个人都至少抢到一分钱，那么首先给每个人分配1分钱
- 2.剩下的钱再随机分给每个人，Ruby的随机函数是平均分布的，因此如果需要使红包金额近似正态分布，需要对平均分布进行Box–Muller转换操作
- 3.由于精度问题，最后一个红包需要用总的红包金额－已分配的金额
- 4.得到服从正态分布的随机数的基本思想是先得到服从均匀分布的随机数，再将服从均匀分布的随机数转变为服从正态分布
Box-Muller
Box-Muller是产生随机数的一种方法。Box-Muller算法隐含的原理非常深奥，但结果却是相当简单。如果在（0,1]值域内有两个一致的随机数字U1和U2，可以使用以下两个等式中的任一个算出一个正态分布的随机数字Z：
- Z=Rcos(θ)或Z=Rsin(θ)
- 其中，R=sqrt(-2ln(U2));θ=2π*U1
- 正态值Z有一个等于0的平均值和一个等于1的标准偏差，可使用以下等式将Z映射到一个平均值为m、标准偏差为sd的统计量X：
- X=m+(Z*sd)
测试：
generateMoneyVector(1, 3) [0.42, 0.38, 0.2] [0.49, 0.06, 0.45] [0.18, 0.54, 0.28] generateMoneyVector(1, 10) [0.13, 0.11, 0.08, 0.13, 0.01, 0.11, 0.04, 0.15, 0.16, 0.08] [0.07, 0.12, 0.11, 0.15, 0.08, 0.05, 0.14, 0.18, 0.03, 0.07] [0.12, 0.08, 0.15, 0.10, 0.11, 0.04, 0.04, 0.10, 0.05, 0.21]