算法思考：红包金额生成
一 背景
最近在整理过去的项目时，回顾了某年红包活动，其中涉及红包金额计算的算法。近些年各家大厂举办的春节红包活动越来越完善，关于活动背后的整体设计介绍、分析、探讨层出不穷。本篇先不关注整体架构，选择红包金额的计算方法作为分析内容。
在当时的项目中，红包金额计算主要是采用了基于一些入参的随机数生成，并且生成的是单个红包金额，并未使用队列方式做预生成。所以再次回顾这个案例，其中其实还有很多可以玩味和深入思考的地方，在这里做一次思考总结。
二 题目描述
要求设计在微信群抢红包的算法，红包总金额为 m 元，分成 n 份，要求返回一个红包金额数组。算法需要满足下面的几条要求：
（1）前 n 个抢红包的人都能抢到钱，第 n 个之后的人直接返回空包，所以这里不做考虑；
（2）每个人能抢到的红包金额是随机的，但随机范围最大化(有机会获得可能的最多金额) ；
（3）抢到红包的每个人，抢到相同金额的概率是一样的。
三 传说中微信红包算法
网上其实可以搜到很多关于红包金额计算方法的解析，例如 微信红包的随机算法是怎样实现的？，给出了一个传说是微信内部人提供的代码：
public static double getRandomMoney(RedPackage _redPackage){
//remainSize 剩余的红包数量
//remainMoney 剩余的钱
if(_redPackage.remainSize == 1){
_redPackage.remainSize--;
return (double) Math.round(_redPackage.remainMoney * 100)/100;
}
Random r = new Random();
double min = 0.01;
double max = _redPackage.remainMoney / _redPackage.remainSize * 2;
double money = r.nextDouble() * max;
money = money <= min ? 0.01 : mondy;
money = Math.floor(money * 100) / 100;
_redPackage.remainSize--;
_redPackage.remainMoney -= money;
return money;
}当然，double 类型显然是不靠谱的，楼主也做了补充，商业计算需要使用 java.math.BigDecimal；并且在回答中提供了测试结果，包括金额分布情况。
四 一个朴素且简单的思考实现
4.1 分析
如果我们自己从头思考，那么会考虑怎样来实现呢？一个简单的方法，n 个人，生成 n 次金额数据，当然，我们也要保证 n 次的金额综合=m 元，且每次每人领取到的金额最小值是 0.01 元，也就是一分钱；最大值是当前的剩余金额-剩余人数。例如总金额 1 元，5 个人可抢，那么第一个人可以抽到的最大金额是 0.96 元，之后每个人领取一元，这是最极端的情况。
其次，上面的这种算法是否能够保证绝对随机？如果不能，那么我们是否有修正策略来做个补救？争取让每个人可能获得的金额尽可能的达到随机效果？
当然，如果能从算法上直接解决是最好的。但如果短时间想不到能够最为符合要求的算法，那么就只能考虑这种补救方法，虽然效率上要差一些，但可以符合要求。既然生成的金额数组可能不是绝对平均，那么我们再生成一次随机数组，调整初始金额数组中各元素的顺序，做个随机乱序，那么就可以接近题目要求的效果。
4.2 一个代码实现（未优化）
public int[] createRandomArr(int m, int n) throws Exception{
int[] ret = new int[n];
int total = m*100;
Random random = new Random();
int cur = 1;
int curSum = 0;
while(cur <= n-1){
int curLeft = total-curSum-(n-cur);
int curAcount = random.nextInt(curLeft);
curAcount = 1+curAcount;
ret[cur-1] = curAcount;
curSum+=curAcount;
cur++;
}
ret[n-1] = total-curSum;
int[] newRet = new int[n];
Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
for(int i=0;i<n;i++){
int index = random.nextInt(n);
while(map.containsKey(index)){
index = random.nextInt(n);
}
newRet[i] = ret[index];
map.put(index, true);
}
return newRet;
}五 再次思考
当然，上面的算法非常粗糙，不过也勉强能达到题目的大部分要求。影响效率严重的地方就是在生成随机索引数组，也就是第 22 行。上面的示例代码是通过 while 循环来实现的。这里可以考虑通过分段优化的方式来避免 while 循环。事实上，如果 java 中有类似 php 中 shuffle（洗牌，做数组随机乱序）的方法，那么就可以直接使用来做第二步的乱序逻辑了。更多的优化，留给大家来思考了。
随机生成红包金额，初见看起来似乎并不难，但怎样保证真正的随机且平均，并不是一个容易解决的问题。无论那种语言，我们能够调用的函数大多数都是伪随机算法，所以并不能保证这点。因此为了达到正态分布等等符合更高要求的效果，就需要对算法做好设计并进行充分的验证，确保多次实验的结果能够达到预期，这期间也需要多次验证和调优的过程。
腾讯云开发者
