木匣子

Web/Game/Programming/Life etc.

微信红包分配算法

最近在微信群里抢红包,经过观察,其规则如下:

发红包时

  • 总额不得少于份数 * 0.01 元

抢红包时

  • 每份至少能够分到 0.01 元
  • 每份累加起来总是等于总额
  • 每份的数额是随机的
  • 先抢或后抢并没有明显优势

要如何实现分配算法,能够满足这一需求?

我的第一反应是可以参考遗传算法中的「轮盘赌」权重分配:假定总额为 amount,份数为 n,算法首先随机产生 n 个权重 weight(s),然后计算权重总和 total,每个领取红包的人得到一个权重 weight_i,然后从总额中取走 weight_i / total * amount 即可。

但由于规则中的货币不可无限细分,而是以 0.01 元为最小单位;此外还要保证每个人至少能得到 0.01 元。所以在取钱的时候要做一些限定:

  • 上限不超过 (剩余总额 - (剩余份数 - 1) * 0.01 元):给后来者留下足够的余额
  • 下限不低于 0.01 元:保底安慰奖

以下是用 javascript 写的 demo,为了避免浮点数精度问题,这里的单位为 1 分,即 0.01 元:

var amount = 100; // cent
var n = 10;

var weights = []
var total = 0
for(var i = 0; i < n; i++) {
    var weight = Math.random();
    weights.push(weight);
    total += weight;
}

var balance = amount;
var count = n;

var takes = [];
while(count > 0) {
    var weight = weights[n - count];
    var take = Math.ceil(weight / total * amount);
    take = Math.max(1, Math.min(take, balance - (count - 1)));

    takes.push(take);
    balance -= take;
    count -= 1;
}

// weights
// [0.7933445337694138, 0.0034502430353313684, 0.39447791734710336, 0.29893025243654847, 0.6303203923162073, 0.5726003672461957, 0.9000553076621145, 0.1479424126446247, 0.4969204587396234, 0.4672785080038011]

// takes
// [17, 1, 9, 7, 14, 13, 20, 4, 11, 4]

这一算法有以下优点:

  • 随机权重预分配的方法很容易实现;
  • 以分为单位,很简单就避开了小数浮点精度问题;
  • 保证所有的钱都被取完,总是使用向上取整;
  • 上下限的控制保证了规则中最小额度的问题;

用向下取整,最后可能会剩出一些钱,可以留给最后一个人;
用向上取整,最后一个人可能取不到原本应得的额度,但是不需要处理余额;

此外,我也围观了一些别人的思路,除了与我想法相同的以外,还有一些其它的思路:

  1. 正态分布:从总额为单位 1 的角度思考,进行随机划分。算法比较复杂,另外还要考虑标准差来影响贫富差距;
  2. 先到先得:不作预处理,先抢的人,先从余额里取走随机额度。这种方法可控性太差,有可能出现先抢的人拿走决大部分,而越是后来者只能得越少;

参考资料


2016-02-29 更新:官方的方案还真的是不作预处理,先到先得: 微信红包的架构设计简介