本文由腾讯梁中原分享，原题“红包算法揭秘！哪段代码让你只抢了0.01元？”，下文进行了排版和内容优化等。
在上一篇《》的文章中，有用户提到想了解自己每次微信红包只能抽中 0.01 元的反向手气最佳是怎么在技术上实现的，于是就有了本篇文章的诞生。
其实，微信红包最初在产品设计上有过很多思路，最初曾以多档次、按比例分配的方式，但最后大家试用下来发现还是随机才好玩。那种看到有人抢到 100 块，有人 0.01 元的快乐无以言喻。
最初的随机算法中，领取越早获得大额红包几率越高，为了避免抢红包变成一个拼手速的游戏，后来的随机算法也对随机范围区间进行了一定调整。
本文中，我们将介绍几种主流的im红包分配算法，相信聪明的你一定能从中窥见微信红包技术实现的一些奥秘。
技术交流：
- 移动端im开发入门文章：《》
- 开源im框架源码：（）
）
《》
《》
《》
《》
《》
《》
《》
《》
《》
《》
《》
《》
《》（* 本文）
普通随机法，简单来说其实就是剩余值随机。
普通随机：用余下的值为最大区间进行随机，但可能不均匀，有些人一把随到99，下面很多人都没得随机了。
以下是算法示例：
// 剩余值随机 ，优点：逻辑简单，缺点：随机区间步步减少，可以明显看出随机值的递减特性，
对后面玩家极不公平，且容易被抓到规律，造成舆论不满。
// 做抢红包体验很差，稍微弥补一点的方案：shuffle一下随机数组，让看起来不那么递减明显。
$res = leftmoneyredbag($moneys, $usernums, $iseveryhave);
//余值随机红包算法 ，一般都是使用剩余值在计算一把。
function leftmoneyredbag($moneys, $usernums, $iseveryhave = 1, $basemoney = 1)
{
if ($moneys <= 0 || $usernums <= 0) {
return ['code' => -3, 'msg' => '红包金额或拆红包总人数不合法'];
}
if ($iseveryhave && $usernums > $moneys) {
return ['code' => -4, 'msg' => '红包数量不足'];
}
//是否每个人都必有
if ($iseveryhave) {
$moneys = $moneys - ($usernums * $basemoney); //此时剩余money可能会无法随机到每一个人
}
$usermoney = [];
//正式执行余值随机
$leftmoneys = $moneys; //可能 50分钱 分100人
$leftusernums = $usernums;
while ($leftusernums > 1) { // 考虑：就一个用户瓜分
// echo "leftmoneys = " . $leftmoneys . " , leftusernums = " . $leftusernums . "
";
$randval = 0;
if ($leftmoneys > 0) { //考虑：剩余的钱不够分
$randval = mt_rand(0, $leftmoneys);
$leftmoneys = $leftmoneys - $randval;
}
$usermoney[] = $iseveryhave ? ($basemoney $randval) : $randval;
$leftusernums--;
}
//最后一位。考虑：剩余的钱太多或者就一个人
$usermoney[] = $iseveryhave ? ($basemoney $leftmoneys) : $leftmoneys;
echo "总数：" . count($usermoney) . "
";
var_dump($usermoney);
echo "总值：" . array_sum($usermoney) . "
";
return ['code' => 0, 'msg' => "success", 'redbag' => $usermoney];
}
“mt_rand(1, 2); ”：mt_rand 包含区间前后边界的，即包含最大值和最小值 ，1和2都会出现。
正常的算法，定好每个人的最小值，然后就是定下随机区间问题。
二倍均值：实际上就是，用剩下金额的两倍均值为最大区间进行随机，相对正态分布，区间相对合适。但人数越接近总额，分布越均匀。也可以三倍、四倍，倍数越高越随机，正态分布越扁平。
以下是算法示例：
$moneys = 99 * 10; //单位为分
$usernums = 990;
$iseveryhave = 0; //是否每个人都有
$res = doublemeanredbag($moneys, $usernums);
// var_dump($res);
//二倍均值算法
function doublemeanredbag($moneys, $usernums, $iseveryhave = 1, $basemoney = 1)
{
if ($moneys <= 0 || $usernums <= 0) {
return ['code' => -3, 'msg' => '红包金额或拆红包总人数不合法'];
}
if ($iseveryhave && $usernums > $moneys) {
return ['code' => -4, 'msg' => '红包数量不足'];
}
//是否每个人都必有
if ($iseveryhave) {
$moneys = $moneys - ($usernums * $basemoney); //此时money可能会无法随机到每一个人
}
$usermoney = [];
//正式执行二倍均值
$leftmoneys = $moneys; //可能 50分钱 分100人
$leftusernums = $usernums;
while ($leftusernums > 1) { // 考虑：就一个用户瓜分
// echo "leftmoneys = " . $leftmoneys . " , leftusernums = " . $leftusernums . "
";
$randval = 0;
if ($leftmoneys > 0) { //考虑：剩余的钱不够分
$doublemeans = ceil($leftmoneys / $leftusernums * 2);
$randval = mt_rand(0, $doublemeans);
$leftmoneys = $leftmoneys - $randval;
}
$usermoney[] = $iseveryhave ? ($basemoney $randval) : $randval;
$leftusernums--;
}
//最后一位。考虑：剩余的钱太多
$usermoney[] = $iseveryhave ? ($basemoney $leftmoneys) : $leftmoneys;
// echo "总数：" . count($usermoney) . "
";
// var_dump($usermoney);
// echo "总值：" . array_sum($usermoney) . "
";
return ['code' => 0, 'msg' => "success", 'redbag' => $usermoney];
}
线段分割是相对合理的红包算法，但实现逻辑会更复杂一些。
红包金额如果想随机分成 n 份，可以处理为：一个线段，随机选择 n-1 点进行切割。
以下内容将详细讲解线段分割算法。
以下是常规线段分割算法示例：
//线段分割算法 -- 有个致命缺陷，随机值碰撞，分割数量越接近总金额，碰撞概率越大 ，所以最好 usernum数量与总金额差的越大越好
function linesegmentredbag($moneys, $usernums, $iseveryhave = 1, $basemoney = 1)
{
if ($moneys <= 0 || $usernums <= 0) {
return ['code' => -3, 'msg' => '红包金额或拆红包总人数不合法'];
}
if ($iseveryhave && $usernums > $moneys) {
return ['code' => -4, 'msg' => '红包数量不足'];
}
$cutpoints = []; //切割点数组
$pointnums = $usernums - 1; //存放的
$usermoney = []; //每一个用户该分得的钱
//正式线段分割，完全随机
// $j = 0;
// 当 用户数 和 总金额差距不大时，这种写法效率极差
while ($pointnums > 0) {
if ($iseveryhave == 1) {
$randval = mt_rand(1, $moneys - 1); //每个人都有，mt_rand包含区间边界的，即包含最大值 和 最小值 ，1和2都会出现
} else {
$randval = mt_rand(0, $moneys); //所有用户，全区间随机，保证了公平，所有人概率一致 0~10。如果$moneys设置-1，导致最后一位必定不为0
}
if (in_array($randval, $cutpoints)) { //这边会产生随机碰撞，500个随机需要2500次左右才能覆盖。
// $j ;
continue;
}
$cutpoints[] = $randval;
$pointnums--;
}
// echo "无效循环次数：" . $j . "
";
// echo "最终切割点数组数量：" . count($cutpoints) . "
";
// var_dump($cutpoints);
// return;
//根据cutpoint计算每个人所得 同时考虑：就一个人
$lastval = 0;
if (count($cutpoints) > 0) {
sort($cutpoints);
foreach ($cutpoints as $randpoint) {
$usermoney[] = $randpoint - $lastval;
$lastval = $randpoint;
}
}
$lastdiff = $moneys - $lastval;
$usermoney[] = $lastdiff;
// echo "总数：" . count($usermoney) . "
";
// echo "总值：" . array_sum($usermoney) . "
";
return ['code' => 0, 'msg' => "success", 'redbag' => $usermoney];
}
以下是array_rand优化后的线段分割算法示例：
//利用array_rand一次拿出多个随机值时，随机且去重,且随机区间包括首尾。
function linesegmentoptimize($moneys, $usernums, $iseveryhave = 1) //$basemoney = 1默认为1
{
if ($moneys <= 0 || $usernums <= 0) {
return ['code' => -3, 'msg' => '红包金额或拆红包总人数不合法'];
}
if ($iseveryhave && $usernums > $moneys) {
return ['code' => -4, 'msg' => '红包数量不足'];
}
$cutpoints = [];
$usermoney = [];
if ($iseveryhave) {
$moneysarr = array_fill(1, $moneys - 1, 0); //转成数组时,去掉头尾得-1，如果10，则下标是1-9
} else {
$moneysarr = array_fill(0, $moneys 1, 0); //转成数组,为了保留头尾得 1，如果10，则下标是0-10，array_rand区间包含首尾
}
if ($usernums == 1) {
$usermoney[] = $moneys;
return ['code' => 0, 'msg' => "success", 'redbag' => $usermoney];
}
$cutpoints = array_rand($moneysarr, $usernums - 1); //多随机、且去重、且区间包含首尾，array_rand第二个值不可为0
sort($cutpoints);
$lastval = 0;
foreach ($cutpoints as $randpoint) {
$diff = $randpoint - $lastval;
$usermoney[] = $diff;
$lastval = $randpoint;
}
$lastdiff = $moneys - $lastval;
$usermoney[] = $lastdiff;
// echo "总数：" . count($usermoney) . "
";
// var_dump($usermoney);
// echo "总值：" . array_sum($usermoney) . "
";
return ['code' => 0, 'msg' => "success", 'redbag' => $usermoney];
}
在写线段分割算法时，发现当全区间 mt_rand 后，出现重复切点需要去重，生成非重复的切点。
这里第一时间想到了使用 array_rand，但不确定 array_rand 的随机特性，不知道它的随机特性是否有去重处理。
经过验证：array_rand($arr, 8) 同时随机取多个索引下标时有去重处理，且随机特性很好。
事实证明：array_rand 一次拿出多个随机值时，随机且去重，且随机区间包括首尾。
代码示例如下：
$res = checkrand(10, 10000);
var_dump($res);
function checkrand($range, $num)
{
$statiarr = array_fill(0, 100, 0);
$sourcearr = range(0, 99);
for ($i = 0; $i < 10000; $i ) {
$indexarr = array_rand($sourcearr, 4); //array_rand随机性可以，且去重性也可以
foreach ($indexarr as $index) { //中途也用array_unique统计，是否单把拿值重复
$statiarr[$index] ;
}
}
return $statiarr;
}
一次随机取2个时，平均200左右：
1 array(100) { [0]=> int(196) [1]=> int(210) [2]=> int(206) [3]=> int(202) ，，，，[97]=> int(196) [98]=> int(197) [99]=> int(188) }
一次随机取4个时，平均400左右：
1array(100) { [0]=> int(372) [1]=> int(428) [2]=> int(394) [3]=> int(441) ,,,,, [97]=> int(382) [98]=> int(388) [99]=> int(358) }
一次随机取99个时，平均9900左右：
1array(100) { [0]=> int(9892) [1]=> int(9890) [2]=> int(9913) [3]=> int(9909) ,,,,[97]=> int(9908) [98]=> int(9903) [99]=> int(9908) }
事实证明：array_rand一次拿出多个随机值时，随机且去重。
最后，我们对全文提到的红包算法的随机性以及计算性价比进行一个整体比较。
以下是测试代码：
function microtime_float()
{
//$usec 精确到微秒 ，$sec 秒 1秒(second) = 1000毫秒(millisecond) = 1000,000微秒(microsecond)
list($usec, $sec) = explode(' ', microtime());
return ((float)$usec (float)$sec); //float保留小数点后四位
}
$startime = microtime_float(); //0.35529400 1616661516
for ($i = 0; $i < 100000; $i ) {
linesegmentredbag($moneys, $usernums, $iseveryhave);
// linesegmentoptimize($moneys, $usernums, $iseveryhave);
// doublemeanredbag($moneys, $usernums, $iseveryhave);
}
$endtime = microtime_float();
$diff = floatval($endtime) - floatval($startime);
echo "线段分割时间差：" . floatval($diff) . "
"; //时间差：0.33733010292053 //optimize时间差：0.11269283294678
exit;
如上图所示：线段分割算法与二倍均值相比，随机区间更大。
如上图所示：线段分割普通版，随着红包总额与红包人数相近时（即切点接近总值时），随机碰撞率显著升高，性能下降。但经过优化后的线段分割算法，性能比二倍均值还优秀。
[1]
[2]
[3]
[4]
[5]
[6]
[7] 》
[8] 》
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
）
作者： (点击作者姓名进入github)
出处：
交流：欢迎加入即时通讯开发交流群
讨论：
jack jiang同时是和的作者，可前往下载交流。
本博文
欢迎转载，转载请注明出处（也可前往 找到我）。