在游戲里面有各種“隨機(jī)”的需求妥凳，比如從n個用戶里面隨機(jī)給m個發(fā)獎勵。那么码泛，要如何實現(xiàn)呢猾封？簡單的來說，可以調(diào)一個stl的函數(shù)來實現(xiàn)噪珊，偽代碼如下：
vector<int> foo(vector<int> & player, int m)
{
std::random_shuffle(players.begin(), players.end());
vector<int> result;
for (size_t i = 0; i < m; i++)
{
result.push_back(players[i]);
}
return result;
}
那shuffle背后是怎么實現(xiàn)的呢晌缘？或者說如何設(shè)計高效并且保證隨機(jī)概率是相同的洗牌算法呢？
1. 不帶權(quán)重的隨機(jī)洗牌算法
最笨的方法
從數(shù)組里面隨機(jī)拿出兩個元素痢站，進(jìn)行交換磷箕。完成一次洗牌。不停的重復(fù)以上過程阵难。重復(fù)k次岳枷。當(dāng)k足夠大的時候，就洗均勻了呜叫。這個方法沒什么好說的空繁，除了簡單以外就全是缺點了。Yates洗牌
這個方法是一個很古老的方法朱庆，非常好理解盛泡。思路是是每次從數(shù)組里面隨機(jī)抽一個元素，放到另外的結(jié)果集中娱颊。然后不停的重復(fù)上述過程傲诵，直到抽出m個凯砍。但是，由于這個方法要每次對數(shù)組的元素進(jìn)行刪除拴竹，所以悟衩，時間復(fù)雜度為O(m*n) 。knuth洗牌 （高德納洗牌）
算法的思路是栓拜，從頭開始遍歷數(shù)組座泳，對于下標(biāo)是i的元素，從i到n之間隨機(jī)出一個下標(biāo)菱属，對這個元素進(jìn)行交換钳榨。
偽代碼的流程是：
for i in (0, n)
從i 到 n隨機(jī)出一個數(shù)j
交換a[j] 和 a[i]
知乎上有個很有意思的問題有哪些驚艷你的算法？纽门，也提到了這個洗牌算法薛耻。
有哪些算法驚艷到了你？ - 劉宇波的回答 - 知乎
https://www.zhihu.com/question/26934313/answer/743798587
小結(jié)：
knuth算法保留了原數(shù)組的所有元素赏陵，僅改變了元素的順序饼齿，時間復(fù)雜度為O(m)。
2. 帶權(quán)重的隨機(jī)洗牌算法
上述討論的問題是“如何公平的從長度是n的數(shù)組里面隨機(jī)出m個”蝙搔，這里的假設(shè)是每個元素被隨機(jī)出來的概率是相同的缕溉。
那問題再復(fù)雜些，希望實現(xiàn)“非公平抽獎”吃型，比如：一個集合里有 n 個元素证鸥，每個元素有不同的權(quán)重，現(xiàn)在要不放回地隨機(jī)抽取 m 個元素勤晚，每個元素被抽中的概率為元素的權(quán)重占總權(quán)重的比例枉层。
- 樸素帶權(quán)重抽樣方法
簡化下問題模式，假設(shè)權(quán)重的和為1赐写，只抽一個人獲獎m=1鸟蜡。比如 ：a,b,c,d 的權(quán)重分別是 0.1，0.3挺邀，0.2揉忘，0.4，從里面選一個中獎端铛。
那這個就很簡單了泣矛，從0~1之間隨機(jī)一個數(shù)，這個數(shù)落在誰的區(qū)間上禾蚕，就算誰中獎乳蓄。
|-0.1-|---0.3---|--0.2--|----0.4----|
^ ^ ^ ^
a b c d
數(shù)學(xué)的原理很簡單，可以理解為 上面的線段上隨機(jī)出一個數(shù)字夕膀，誰占的長度多（概率大就是長度多）虚倒，那么誰中獎的概率就大。
剛才是問題的簡化版本 m=1(只有一個人中獎）产舞，如果希望是m=2的話魂奥，就重復(fù)上述過程m次。當(dāng)有人抽到了易猫，就把它移除出來耻煤，然后再重復(fù)。
# m=1只有一個人抽獎的情況
# weight_data 的數(shù)據(jù)類型為 dict
def random_weight(weight_data):
total = sum(weight_data.values()) # 權(quán)重求和
ra = random.uniform(0, total) # 在0與權(quán)重和之前獲取一個隨機(jī)數(shù)
curr_sum = 0
ret = None
keys = weight_data.keys() # 使用Python3.x中的keys
for k in keys:
curr_sum += weight_data[k] # 在遍歷中准颓，累加當(dāng)前權(quán)重值
if ra <= curr_sum: # 當(dāng)隨機(jī)數(shù)<=當(dāng)前權(quán)重和時哈蝇，返回權(quán)重key
ret = k
break
return ret
# 當(dāng)需要 m > 1的時
def foo(data, N):
results = []
i = 0
while i < N:
m = random_weight(data) # 重復(fù)n次
if m in results:
continue
results.append(m)
i = i+1
return results
小結(jié)：
如果要選取 m 個元素，則可以按上面的方法先選取一個攘已，將該元素從集合中去除炮赦，再反復(fù)按上面的方法抽取剩余的元素。這種方法的復(fù)雜度是 O(mn)样勃，并且將元素從集合中刪除其實不太方便實現(xiàn)吠勘。
對于帶權(quán)重抽樣，有兩個更好的方法來解決樸素帶權(quán)重抽樣的一些弊端峡眶，具體的細(xì)節(jié)在這里：
- A-Res 算法論文 Weighted Random Sampling
- A-ExpJ 算法
參考：
