Python利用帶權重隨機數解決抽獎和游

關於帶權隨機數

為了幫助理解，先來看三類隨機問題的對比：

1.已有n條記錄，從中選取m條記錄，選取出來的記錄前後順序不管。

實現思路：按行遍歷所有記錄，約隔n/m條取一個數據即可

2.在1類情況下，還要求選取出來的m條記錄是隨機排序的

實現思路：給n條記錄，分別增加一列標記，值為隨機選取的1至n之間的不重複數據。

3.區別於1,2類問題，如果記錄是有權重的，如何結合權重去隨機選取。比如A的權重為10， B的權重股為5， C的權重為1，則隨機選取4個時可能應該出現AABB。

第3類問題便是本文重點了。

實現思路：以 A:10， B:5， C:1 三條記錄上隨機選取4條為例，（是否以權重排序這個無所謂）

對於

A 10

B 5

C 1

首先，將第n行的數值賦為第n行加第n-1行的，遞歸執行，如下：

A 10

B 15

C 16

然後每次從[1,16]隨機選取一個數，如果落在[1,10]之間，則選取A，如果落在(10,15]之間則選B，如果落在(16,16]之間則選取C，圖示如下，誰占的區間大（權重高），被選上的概率更大。

在抽獎和遊戲爆裝備中的運用

帶權隨機在遊戲開發中重度使用,各種抽獎和爆裝備等.

運營根據需要來配置各個物品出現的概率.

今天要說的這個帶權隨機演算法思想很簡單,就是"把所有物品根據其權重構成一個個區間,權重大的區間大.可以想像成一個餅圖. 然後,扔骰子,看落在哪個區間,"

舉個栗子,有個年終抽獎,物品是iphone/ipad/itouch.

主辦方配置的權重是[('iphone', 10), ('ipad', 40), ('itouch', 50)].

用一行程式碼即可說明其思想,即random.choice(['iphone']*10 + ['ipad']*40 + ['itouch']*50).

下面,我們寫成一個通用函數.

上面的程式碼夠直觀,不過細心的會發現,每次都會計算total,每次都會線性遍歷區間進行減操作.其實我們可以先存起來,查表就行了.利用accumulate+bisect二分查找.

物品越多,二分查找提升的性能越明顯.