一個「偽」亂數的演算法

這是前一陣子從 "Game Code Complete" 裡看到的演算法。

說是「偽」亂數，因為它並不夠亂。但是它非常節省效能。

 

需求是這樣:

有某個數量的獎品，我們希望每次亂數取出一個來，不能重複，而且每個都要取到。

演算法是這樣:

假設獎品數量為 member，比 member 大的一個質數為 prime，

首先先取三個亂數 RandomA, RandomB, RandomC

計算

Skip = RandomA * member * member + RandomB * member + RandomC

取得 Skip 數值後，在每次需要取亂數數值時，

nextNumber += Skip

nextNumber %= prime

也就是，每次計算時，把前一次的數值加上 Skip, 然後用這個質數來取餘數, 這樣算出來的 nextNumber 就絕對不會重複。當然餘數可能會比 member 數量還大，那就再計算一次，取下一個。

 

看完之後，霎時間覺得很神奇，一時半刻還想不透，於是用試算表建公式來算，果然，產生了一個不會重複數字的序列。

但是，從這序列也發現了缺點。就是取出來的數值是有某種規律的，而且規律很明顯。不過如果不把數列排出來，也不容易發現就是了。

效能是這個演算法最大的優點，每次取亂數只需要一個加法跟一個取餘數的運算。

 

再深入去看，這演算法還可以多做一些簡化。

Skip 這個數值，只要取小於 prime，大於 0 ( 最好也不要等於 1 ) 的數值就可以，不需要取三個亂數再去加減乘除。

取出的數值的規律是，從第一個取出的 nextNumber 開始，每次遞增 Skip 指定的數量，超過 prime 的時候，再回到 0 繼續算，而之所以會全部都選取到的原因，就是因為質數的特性 -- 只能被 1 與自己整除。

 

這個演算法可以用在什麼地方呢?

分配掉寶當然是不能用啦，這個數列太過規律了。但是任務物品的掉落倒是可以用得上，怪物的重生也可以用，適用的場合應該還不少。