最近的一個業(yè)務(wù)需求是開發(fā)一個抽獎管理功能，要求在一個獎池中放一堆獎品，分別給它們設(shè)置不同的數(shù)量和概率，在獎品沒有發(fā)完的情況下，概率高的被抽中的幾率就大，反之則低。另外，概率為0的不能被抽中，概率為100則一定要被抽中。
這里只討論下其中的核心算法的設(shè)計及一個示例函數(shù)，算法之外的系統(tǒng)控制暫不提及。
實現(xiàn)抽獎的方法應(yīng)該有很多，沒有仔細去考察和搜索那些非常復雜的算法，這里僅做了一個簡單的假設(shè)，并在此基礎(chǔ)上推出后面所有的控制邏輯。
- 基本假設(shè)
假設(shè)系統(tǒng)生成一個1到100之間的隨機整數(shù)R，C為1到100之間的一個任意整數(shù)，那么R小于C的概率為C/100。
暫且不去從數(shù)學上論證這個假設(shè)是否真的成立，我們僅從直觀上來看，R是隨機的，它的值不論是多少，取到1-100之間任意一個整數(shù)的概率都是一樣的。
但C越小，R落入0-C之間的概率也會越小，所以我們大致上可以用C來控制某個獎品的概率。Good!
- 實現(xiàn)邏輯
有了上面的假設(shè)，我們就可以考慮實現(xiàn)一個獎池內(nèi)不同獎品配置情況下的控制邏輯。
首先我們把獎池中的獎品做一個過濾，剔除掉那些不滿足條件的獎品，比如概率為0的、已經(jīng)發(fā)完的等等。剩下的獎品都是可以被抽中的，只是概率大小不同而已。
OK，下面我們來設(shè)置一些概念，以方便后面的行文。
假設(shè)有N個獎品，它們都以100為滿概率，那么它們總共的概率空間為O=N*100；
如果這N個獎品的概率分別為C1,C2,C3...Cn，那么他們總共的中獎概率空間就是H=C1+C2+C3+...+Cn，因為Cn總是小于等于100，所以
H總是小于等于O。
我們把以上這些參數(shù)在后臺配置好，當抽獎行為發(fā)生時，我們讓系統(tǒng)生成一個隨機數(shù)R，1<=R<=O，那么當R<=C時，我們就認為中獎了，否則就不中獎。Good10!
在判斷出是否中獎后，我們就可以進一步判斷中了什么獎。
首先把獎品以數(shù)組形式A按概率從小到大進行排序，然后求出每個獎品在總中獎概率空間H中的中獎區(qū)間，并且把各區(qū)間的最大值保存成一個數(shù)組D。
例如有a和b兩個獎品，概率分別為20和30,那么a的概率空間為20，中獎區(qū)間為1-20；而b的概率空間為30，但它的中獎區(qū)間是20-50，這樣D就是(1,20,50)。
然后我們再把D從小到大排序并循環(huán)，當R小于20時，我們認為a被抽中；R小于50時，認為b被抽中。Good11!
這里有個問題，就是為什么不直接把R跟a和b的概率比較，而要比較它們各自中間區(qū)間的最大值？
因為我們設(shè)想的情況是，不僅某種獎品概率調(diào)大時其抽中的幾率增大，而且所有獎品的概率都調(diào)大時，它們被抽中的幾率都增大。
如果直接把R跟獎品各自的概率比較，根據(jù)我們上面的邏輯，它們總的中獎空間H=2×100=200，只要R的值小于200，我們就已經(jīng)認為中獎了；但是當a和b兩種獎品的概率為99時，只有當R小于100時它們才會被抽中，R落在100到200之間將不被認為中獎，這顯然是不對的。
搞清楚了上面的邏輯，剩下的就是處理一些特殊情況了。
比如，如果某些獎品的概率為100，這就是我們之前說的存在滿概率獎品。按我們的設(shè)想，當有百分百中獎的獎品時，我們一定要這種獎品被抽中。
處理這個問題，我的方法是把獎品按概率分成兩組，一組是滿概率獎品，一組是非滿概率獎品。當滿概率獎品組不為空時，從中隨機取出一個作為被抽中的獎品放出，直到這些獎品被抽完。
到此為止整個邏輯基本結(jié)束，可以著手寫代碼了。Good101!
/**
* 抽獎核心算法
* @param prize array,所有概率不為0且剩余數(shù)大于0的獎品數(shù)組
* @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();//中獎區(qū)間分界數(shù)組
$full_chance_prize = $nofull_chance_prize = array();//劃分滿概率和非滿概率數(shù)組
$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并生成概率數(shù)組
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];
}
}
}
}
/**
* 輔助函數(shù)array_isum，計算數(shù)組中i起n個數(shù)的和
* @params $input array,要計算的數(shù)組
* @params $start,int,起始位置
* @params $num,int,個數(shù)
* @return int
*/
function array_isum($input,$start,$num){
$temp = array_slice($input, $start,$num);
return array_sum($temp);
}
上面是用PHP實現(xiàn)的一個核心算法，其中定義了一個常量FULL_CHANCE為100。還定義了一個輔助函數(shù)array_isum，用來計算一個數(shù)組中從下標i開始n個數(shù)的和。
這里面其實還有一個小小的問題，就是當幾種獎品都是非滿概率獎品且它們的概率相同，我們需要隨機抽出一個作為獎品放出，如果不做這個處理，則會按照默認順序先把前面的獎品發(fā)完再發(fā)后面的。
Enjoy It!
