抽奖概率-三种算法-白红宇的个人博客

抽奖概率-三种算法

发布日期：2021-08-15 22:29:43 浏览次数：34 分类：技术文章

本文共 2850 字，大约阅读时间需要 9 分钟。

最近接触到一个抽奖需求，加上平时玩的暗黑3很少掉暗金装备，就抽空学习下这类概率问题，暂时按网络称为掉宝类型概率。

例如游戏中打败一个boss，会掉落下面其中一个物品，而每个物品都有一定概率：

1. 靴子 20%

2. 披风 25%

3. 饰品 10%

4. 双手剑 5%

5. 金币袋 40%

现在的问题就是如何根据概率掉落一个物品给玩家。

一. 一般：生成一个列表，分成几个区间，例如列表长度100，1-20是靴子的区间，21-45是披风的区间等，然后随机从100取出一个数，看落在哪个区间。算法时间复杂度：预处理O(MN)，随机数生成O(1)，空间复杂度O(MN)，其中N代表物品种类，M则由最低概率决定。

二、离散算法：也就是上面的改进，竟然1-20都是靴子，21-45都是披风，那抽象成小于等于20的是靴子，大于20且小于等于45是披风，就变成几个点[20,45,55,60,100]，然后也是从1到99随机取一个数R，按顺序在这些点进行比较，知道找到第一个比R大的数的下标，比一般算法减少占用空间，还可以采用二分法找出R，这样，预处理O(N)，随机数生成O(logN)，空间复杂度O(N)。

请点击查看详细：

三、Alias Method

Alias Method就不太好理解，实现很巧妙，推荐先看看这篇文章：

大致意思：把N种可能性拼装成一个方形（整体），分成N列，每列高度为1且最多两种可能性，可能性抽象为某种颜色，即每列最多有两种颜色，且第n列中必有第n种可能性，这里将第n种可能性称为原色。

想象抛出一个硬币，会落在其中一列，并且是落在列上的一种颜色。这样就得到两个数组：一个记录落在原色的概率是多少，记为Prob数组，另一个记录列上非原色的颜色名称，记为Alias数组，若该列只有原色则记为null。

之前的例子，为了便于演示换成分数

1. 靴子 20% -> 1/4

2. 披风 25% -> 1/5

3. 饰品 10% -> 1/10

4. 双手剑 5% -> 1/20

5. 金币袋 40% -> 2/5

然后每个都乘以5（使每列高度为1），再拼凑成方形

拼凑原则：每次都从大于等于1的方块分出一小块，与小于1的方块合成高度为1

alias-method

由上图方形可得到两个数组：

Prob: [3/4, 1/4, 1/2, 1/4, 1]

Alias: [4, 4, 0, 1, null] (记录非原色的下标)

之后就根据Prob和Alias获取其中一个物品

随机产生一列C，再随机产生一个数R，通过与Prob[C]比较，R较大则返回C，反之返回Alias[C]。

Alias Method 复杂度：预处理O(NlogN)，随机数生成O(1)，空间复杂度O(2N)

实现Alias Method

/**

* @desc 拼凑，获得Prob和Alias数组

* @param array $data

* @param array $prob

* @param array $alias

function init(array $data, array &$prob, array &$alias) {

$nums = count($data);

$small = $large = array();

for ($i = 0; $i < $nums; ++$i) {

$data[$i] = $data[$i] * $nums; // 扩大倍数，使每列高度可为1

/** 分到两个数组，便于组合 */

if ($data[$i] < 1) {

$small[] = $i;

} else {

$large[] = $i;

}

/** 将超过1的色块与原色拼凑成1 */

while (!empty($small) && !empty($large)) {

$n_index = array_shift($small);

$a_index = array_shift($large);

$prob[$n_index] = $data[$n_index];

$alias[$n_index] = $a_index;

// 重新调整大色块

$data[$a_index] = ($data[$a_index] + $data[$n_index]) - 1;

if ($data[$a_index] < 1) {

$small[] = $a_index;

} else {

$large[] = $a_index;

}

/** 剩下大色块都设为1 */

while (!empty($large)) {

$n_index = array_shift($large);

$prob[$n_index] = 1;

}

/** 一般是精度问题才会执行这一步 */

while (!empty($small)) {

$n_index = array_shift($small);

$prob[$n_index] = 1;

}

/**

* @desc 获取某种物品

* @param array $prob

* @param array $alias

* @return int

function generation($prob, $alias) {

$nums = count($prob) - 1;

$MAX_P = 100000; // 假设最小的几率是万分之一

$coin_toss = rand(1, $MAX_P) / $MAX_P; // 抛出硬币

$col = rand(0, $nums); // 随机落在一列

$b_head = ($coin_toss < $prob[$col]) ? TRUE : FALSE; // 判断是否落在原色

return $b_head ? $col : $alias[$col];

}

$data = array(0.25, 0.2, 0.1, 0.05, 0.4);

$prob = $alias = array();

init($data, $prob, $alias);

$result = generation($prob, $alias);

$count = array(0, 0, 0, 0, 0);

for ($i = 0; $i < 10000; $i++) {

$result = generation($prob, $alias);

$count[$result]++;

}

echo '<pre>';

print_r($count);

echo '</pre>';

/**

Array

(

[0] => 2463

[1] => 1982

[2] => 972

[3] => 507

[4] => 4076

)

转载于:https://www.cnblogs.com/zhoug2020/p/6396194.html

转载地址：https://blog.csdn.net/weixin_30781107/article/details/97162695 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：一个简洁、好用的Pytorch训练模板

下一篇：c语言作业1

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章