普通随机法
普通随机法，也称为剩余值随机法，是一种在分配红包金额时使用的方法。这种方法的核心思想是在每次分配红包时，从剩余的总金额中随机抽取一部分作为红包金额，然后将剩余的金额继续用于下一次分配。简单来说，就是每次分配后，剩余的金额会随机减少，直到所有红包都被分配完毕。
具体来说，普通随机法的步骤如下：
-
初始化：确定红包的总金额和红包的总数。 -
随机分配：在每次分配红包时，随机选择一个金额，这个金额的范围是从最小可能的红包金额（通常是0.01元）到剩余总金额除以剩余红包数的两倍。 -
更新剩余：每次分配后，从总金额中减去分配出去的红包金额，更新剩余的总金额和红包数。 -
循环分配：重复步骤2和3，直到所有的红包都被分配完毕。 -
保证公平性：为了保证分配的公平性，每次分配的随机金额不会超过剩余总金额除以剩余红包数的两倍。
这种方法的优点是实现简单，且能够保证红包金额的随机性，使得每个参与者都有获得较大红包的机会。然而，它也可能导致某些红包金额特别小，而最后一个红包金额特别大，从而在一定程度上影响红包分配的均匀性。
案例代码
/**
* @desc 剩余值随机红包
* @param int $moneys
* @param int $userNums
* @param bool $isEveryHave
* @param int $baseMoney
* @return array
* @author Tinywan(ShaoBo Wan)
*/
function left_money_redbag(int $moneys, int $userNums, bool $isEveryHave = true, int $baseMoney = 1): array
{
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) { // 考虑：就一个用户瓜分
$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 ' [x] [红包总数] ' . count($userMoney) . PHP_EOL;
echo ' [x] [红包总值] ' . array_sum($userMoney) . PHP_EOL;
return ['code' => 0, 'msg' => "success", 'redbag' => $userMoney];
}
/** 红包总金额 */
$moneys = 10;
/** 参加红包人数 */
$userNums = 3;
/** 是否每个人都必有 */
$isEveryHave = true;
$result = left_money_redbag($moneys, $userNums, $isEveryHave);
print_r($result);运行结果
[x] [红包总数] 3
[x] [红包总值] 10
Array
(
[code] => 0
[msg] => success
[redbag] => Array
(
[0] => 8
[1] => 1
[2] => 1
)
)“
优点：代码实现逻辑简单 缺点：随机区间步步减少，可以明显看出随机值的递减特性，对后面玩家极不公平，且容易被抓到规律，造成舆论不满。
二倍均值算法
二倍均值算法是一种在微信红包分配中广泛使用的算法，旨在实现红包金额的随机分配，同时保持一定的公平性和随机性。
“这种算法的核心思想是：每次分配的红包金额是剩余红包总金额与剩余红包数量的二倍均值的一个随机数。
步骤
“具体步骤如下：
-
初始化：确定红包的总金额 ( M )和红包的总数( N )。 -
计算二倍均值：在每次分配红包时，计算剩余红包金额 ( M ) 与剩余红包数量 ( N ) 的二倍均值，即 ( text{avg} = frac{M'}{N'} times 2 )。 -
随机分配：从0到 ( text{avg} ) 之间随机选择一个金额 ( x ) 作为当前红包的金额。这个随机数 ( x ) 保证了红包金额的随机性，同时也限制了红包金额的上限，避免最后一个红包金额过大。 -
更新剩余：从剩余总金额 ( M ) 中减去分配出去的红包金额 ( x )，更新剩余的总金额 ( M = M - x ) 和红包数 ( N = N - 1 )。 -
循环分配：重复步骤 2-4，直到所有的红包都被分配完毕。 -
保证最后一个红包：在分配最后一个红包时，直接将剩余的总金额分配给最后一个红包，以确保所有红包都被分配。
“二倍均值算法的优点包括：
-
公平性：每个人抢到的红包金额期望值接近相等。 -
随机性：红包金额的分配具有一定的随机性，增加了抢红包的趣味性。 -
避免极端情况：通过限制红包金额的上限，减少了极端红包金额（如0元或极大金额）的出现。
这种算法在微信红包等场景中得到了广泛应用，因为它既满足了用户对红包金额随机性的期待，又在一定程度上保证了分配的公平性。
案例代码
/**
* @desc 二倍均值算法
* @param int $moneys
* @param int $userNums
* @param bool $isEveryHave
* @param int $baseMoney
* @return array
* @author Tinywan(ShaoBo Wan)
*/
function double_mean_redbag(int $moneys, int $userNums, bool $isEveryHave = true, int $baseMoney = 1): array
{
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) { // 考虑：就一个用户瓜分
$RandVal = 0;
if ($leftMoneys > 0) { //考虑：剩余的钱不够分
$doubleMeans = ceil($leftMoneys / $leftUserNums * 2);
$RandVal = mt_rand(0, (int)$doubleMeans);
$leftMoneys = $leftMoneys - $RandVal;
}
$userMoney[] = $isEveryHave ? ($baseMoney + $RandVal) : $RandVal;
$leftUserNums--;
}
// 最后一位。考虑：剩余的钱太多
$userMoney[] = $isEveryHave ? ($baseMoney + $leftMoneys) : $leftMoneys;
echo '[x] [红包总数] ' . count($userMoney) . PHP_EOL;
echo '[x] [红包总值] ' . array_sum($userMoney) . PHP_EOL;
return ['code' => 0, 'msg' => "success", 'redbag' => $userMoney];
}
/** 红包总金额（单位：分） */
$moneys = 10 * 10;
/** 参加红包人数 */
$userNums = 11;
/** 是否每个人都有 */
$isEveryHave = true;
$result = double_mean_redbag($moneys, $userNums, $isEveryHave);
print_r($result);运行结果
[x] [红包总数] 11
[x] [红包总值] 100
Array
(
[code] => 0
[msg] => success
[redbag] => Array
(
[0] => 17
[1] => 16
[2] => 13
[3] => 1
[4] => 3
[5] => 4
[6] => 8
[7] => 5
[8] => 18
[9] => 6
[10] => 9
)
)线段分割算法
线段分割算法通常用于将一个连续的线段分割成多个小线段，这种算法在计算机图形学、计算机辅助设计（CAD）、地理信息系统（GIS）等领域有广泛应用。在微信红包的场景中，线段分割算法可以用于将总金额分割成若干个红包金额。
假设我们有一个总金额 ( M ) 需要分割成 ( N ) 个红包，线段分割算法的基本思想是将 ( M ) 表示为一个长度为 ( M ) 的线段，然后通过某种规则将这个线段分割成 ( N ) 个小线段，每个小线段的长度代表一个红包的金额。
“在微信红包的具体实现中，可能会采用更复杂的线段分割算法，以确保红包金额的随机性和公平性。例如，可以采用以下步骤：
-
初始化：设初始线段长度为 ( M )，红包总数为 ( N )。 -
计算分割点：根据红包分配算法（如二倍均值算法），计算每个红包的金额，并确定分割点。 -
分割线段：在 ( M ) 的长度上，根据计算出的分割点，将线段分割成 ( N ) 个小线段。 -
分配红包：将每个小线段的长度分配给对应的红包。 -
更新线段：每次分配后，更新剩余的线段长度，为下一次分配做准备。 -
结束分配：当所有红包都分配完毕后，结束分配过程。
“线段分割算法在实现时需要考虑算法的效率和公平性，确保在高并发的情况下也能快速准确地分配红包金额。
案例代码
/**
* @desc 线段分割算法
* @param int $moneys
* @param int $userNums
* @param bool $isEveryHave
* @return array
* @author Tinywan(ShaoBo Wan)
*/
function line_segment_redbag(int $moneys, int $userNums, $isEveryHave = true): array
{
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 '[x] [无效循环次数] ' . $j . PHP_EOL;
echo '[x] [最终切割点数组数量] ' . count($cutPoints) . PHP_EOL;
//根据cutPoint计算每个人所得 同时考虑：就一个人
$lastVal = 0;
if (count($cutPoints) > 0) {
sort($cutPoints);
foreach ($cutPoints as $RandPoint) {
$userMoney[] = $RandPoint - $lastVal;
$lastVal = $RandPoint;
}
}
$lastDiff = $moneys - $lastVal;
$userMoney[] = $lastDiff;
echo '[x] [红包总数] ' . count($userMoney) . PHP_EOL;
echo '[x] [红包总值] ' . array_sum($userMoney) . PHP_EOL;
return ['code' => 0, 'msg' => "success", 'redbag' => $userMoney];
}运行结果
[x] [无效循环次数] 0
[x] [最终切割点数组数量] 10
[x] [红包总数] 11
[x] [红包总值] 100
Array
(
[code] => 0
[msg] => success
[redbag] => Array
(
[0] => 10
[1] => 6
[2] => 23
[3] => 1
[4] => 5
[5] => 1
[6] => 4
[7] => 6
[8] => 12
[9] => 28
[10] => 4
)
)算法耗时与效果
图片来源：腾讯云开发者
上图可看出，线段分割算法与二倍均值相比，随机区间更大。
上图可看出，线段分割普通版，随着红包总额与红包人数相近时（即切点接近总值时），随机碰撞率显著升高，性能下降。但经过优化后的线段分割算法，性能比二倍均值还优秀。
版权说明
文章采用： 《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权。版权声明：本站资源来自互联网收集，仅供用于学习和交流，请勿用于商业用途。如有侵权、不妥之处，请联系客服并出示版权证明以便删除!
发表评论