最近的一个业务需求是开发一个抽奖管理功能，要求在一个奖池中放一堆奖品，分别给它们设置不同的数量和概率，在奖品没有发完的情况下，概率高的被抽中的几率就大，反之则低。另外，概率为0的不能被抽中，概率为100则一定要被抽中。
这里只讨论下其中的核心算法的设计及一个示例函数，算法之外的系统控制暂不提及。
实现抽奖的方法应该有很多，没有仔细去考察和搜索那些非常复杂的算法，这里仅做了一个简单的假设，并在此基础上推出后面所有的控制逻辑。
- 基本假设
假设系统生成一个1到100之间的随机整数R，C为1到100之间的一个任意整数，那么R小于C的概率为C/100。
暂且不去从数学上论证这个假设是否真的成立，我们仅从直观上来看，R是随机的，它的值不论是多少，取到1-100之间任意一个整数的概率都是一样的。
但C越小，R落入0-C之间的概率也会越小，所以我们大致上可以用C来控制某个奖品的概率。Good!
- 实现逻辑
有了上面的假设，我们就可以考虑实现一个奖池内不同奖品配置情况下的控制逻辑。
首先我们把奖池中的奖品做一个过滤，剔除掉那些不满足条件的奖品，比如概率为0的、已经发完的等等。剩下的奖品都是可以被抽中的，只是概率大小不同而已。
OK，下面我们来设置一些概念，以方便后面的行文。
假设有N个奖品，它们都以100为满概率，那么它们总共的概率空间为O=N*100；
如果这N个奖品的概率分别为C1,C2,C3...Cn，那么他们总共的中奖概率空间就是H=C1+C2+C3+...+Cn，因为Cn总是小于等于100，所以
H总是小于等于O。
我们把以上这些参数在后台配置好，当抽奖行为发生时，我们让系统生成一个随机数R，1<=R<=O，那么当R<=C时，我们就认为中奖了，否则就不中奖。Good10!
在判断出是否中奖后，我们就可以进一步判断中了什么奖。
首先把奖品以数组形式A按概率从小到大进行排序，然后求出每个奖品在总中奖概率空间H中的中奖区间，并且把各区间的最大值保存成一个数组D。
例如有a和b两个奖品，概率分别为20和30,那么a的概率空间为20，中奖区间为1-20；而b的概率空间为30，但它的中奖区间是20-50，这样D就是(1,20,50)。
然后我们再把D从小到大排序并循环，当R小于20时，我们认为a被抽中；R小于50时，认为b被抽中。Good11!
这里有个问题，就是为什么不直接把R跟a和b的概率比较，而要比较它们各自中间区间的最大值？
因为我们设想的情况是，不仅某种奖品概率调大时其抽中的几率增大，而且所有奖品的概率都调大时，它们被抽中的几率都增大。
如果直接把R跟奖品各自的概率比较，根据我们上面的逻辑，它们总的中奖空间H=2×100=200，只要R的值小于200，我们就已经认为中奖了；但是当a和b两种奖品的概率为99时，只有当R小于100时它们才会被抽中，R落在100到200之间将不被认为中奖，这显然是不对的。
搞清楚了上面的逻辑，剩下的就是处理一些特殊情况了。
比如，如果某些奖品的概率为100，这就是我们之前说的存在满概率奖品。按我们的设想，当有百分百中奖的奖品时，我们一定要这种奖品被抽中。
处理这个问题，我的方法是把奖品按概率分成两组，一组是满概率奖品，一组是非满概率奖品。当满概率奖品组不为空时，从中随机取出一个作为被抽中的奖品放出，直到这些奖品被抽完。
到此为止整个逻辑基本结束，可以着手写代码了。Good101!
/**
* 抽奖核心算法
* @param prize array,所有概率不为0且剩余数大于0的奖品数组
* @return array 单个奖品
* version 2015.12.21
* author thinkmad@sina.com
*/
const FULL_CHANCE = 100;
function calcPrize($prize){
if(!$prize){
return false;
}
$arr_chance = array();//所有奖品概率
$arr_delimiter = array();//中奖区间分界数组
$full_chance_prize = $nofull_chance_prize = array();//划分满概率和非满概率数组
$H = 0;//中奖概率空间
//划分满概率和非满概率奖品
foreach($prize as $item){
if($item['prizeChance'] >= self::FULL_CHANCE) {
$full_chance_prize[] = $item;
}else{
$nofull_chance_prize[$item['prizeID']] = $item;
}
}
//存在满概率奖品，则随机取出一个奖品并返回
$len = count($full_chance_prize);
if($len > 0){
$r = mt_rand(0,$len-1);
return $full_chance_prize[$r];
}
//计算总概率空间O
$O = count($prize) * self::FULL_CHANCE;
//计算总中奖空间H并生成概率数组
foreach($nofull_chance_prize as $k => $v){
$H += $v['prizeChance'];
$arr_chance[$k] = $v["prizeChance"];
}
$R = mt_rand(1,$O);
if($R > $H){ //R不在中奖空间
return false;
}else{//R落在中奖空间
asort($arr_chance);
for($i = 0; $i < count($arr_chance) ; $i++){
$arr_delimiter[key($arr_chance)] = array_isum($arr_chance,0,$i+1);
next($arr_chance);
}
foreach($arr_delimiter as $key => $val){
if($R <= $val) {
return $nofull_chance_prize[$key];
}
}
}
}
/**
* 辅助函数array_isum，计算数组中i起n个数的和
* @params $input array,要计算的数组
* @params $start,int,起始位置
* @params $num,int,个数
* @return int
*/
function array_isum($input,$start,$num){
$temp = array_slice($input, $start,$num);
return array_sum($temp);
}
上面是用PHP实现的一个核心算法，其中定义了一个常量FULL_CHANCE为100。还定义了一个辅助函数array_isum，用来计算一个数组中从下标i开始n个数的和。
这里面其实还有一个小小的问题，就是当几种奖品都是非满概率奖品且它们的概率相同，我们需要随机抽出一个作为奖品放出，如果不做这个处理，则会按照默认顺序先把前面的奖品发完再发后面的。
Enjoy It!
网友评论