規(guī)定范圍內(nèi)一定數(shù)量無重復(fù)隨機(jī)數(shù)的產(chǎn)生算法及應(yīng)用

謝春祥,張兆亮

（蚌埠學(xué)院,安徽蚌埠233030）

規(guī)定范圍內(nèi)一定數(shù)量的隨機(jī)數(shù)的產(chǎn)生在生產(chǎn)研究中有著廣泛的應(yīng)用.通常的隨機(jī)數(shù)產(chǎn)生方法是重復(fù)進(jìn)行生成操作,直到產(chǎn)生足夠數(shù)量的隨機(jī)數(shù)為止.并且為了防止重復(fù),還要不斷掃描對比己經(jīng)生成的隨機(jī)數(shù).這樣效率很低,而且可能陷入死循環(huán)（一直產(chǎn)生不了合格的隨機(jī)數(shù),程序持續(xù)空轉(zhuǎn)）[1-6].本文提出通過“下標(biāo)填充補(bǔ)尾法”,可以有效解決通常方法的弊端,達(dá)到高效可靠的目的.

1 通常產(chǎn)生規(guī)定范圍隨機(jī)數(shù)的方法

要生成符合要求的隨機(jī)數(shù),通常都是先產(chǎn)生一般的隨機(jī)數(shù),再通過特定的方法從中挑選所需要的數(shù).普通隨機(jī)數(shù)的產(chǎn)生常用的rand（）函數(shù)實現(xiàn),例如,要生成一個值在區(qū)間[1,N]內(nèi)的隨機(jī)數(shù)R,代碼如下：

srand（（unsigned）time（NULL））；

R=rand（）%（N+1）；

第1行代碼是給隨機(jī)數(shù)函數(shù)賦一個種子值,以便隨機(jī)函數(shù)在此基礎(chǔ)上遞推出隨機(jī)數(shù)來.這里用不斷變化的計算機(jī)時間做種子.在第2行代碼里,由rand（）函數(shù)產(chǎn)生一個隨機(jī)數(shù).但由于rand（）的返回值在0～327 67之中（一個short整型數(shù)值的范圍）,所以當(dāng)N值小于327 67時,就要將返回值模（N+1）取余,以使值的范圍一定落在[1,N]中.如果要取的隨機(jī)數(shù)值大于327 67,則可由多個rand（）的返回值進(jìn)行線性疊加獲得[2].一定范圍內(nèi)隨機(jī)數(shù)產(chǎn)生了,下面著重探討如何產(chǎn)生規(guī)定數(shù)量的隨機(jī)數(shù).

2 下標(biāo)填充法產(chǎn)生隨機(jī)數(shù)

假設(shè)要產(chǎn)生M個值在區(qū)間[1,N]的隨機(jī)數(shù).常用的方法就是重復(fù)執(zhí)行上面所說的兩行代碼,直到產(chǎn)生M個滿足條件的隨機(jī)數(shù)為止[3-5].但這樣做將要花費(fèi)大量的時間,尤其是當(dāng)M和N很接近時,而且難以滿足無重復(fù)的要求.所以必須找一個新的高效數(shù)法,從根本上解決這個問題.這就是下標(biāo)填充補(bǔ)尾法.

先定義一個長度N的一維數(shù)組,名為A n,將初值全設(shè)為0,數(shù)組下面的格子中顯示的是他們的下標(biāo)；再定義一個長度為M的一維數(shù)組B m.

數(shù)組A n（注意：是一維數(shù)組,下一行是每個元素的位置）

0 1 0 2 3 3 0 4 0 5 6 6 0 7…………0 N-1 0 N

數(shù)組B m

…………M-1 M 6 1 3 2 3 4 5 6 7

算法代碼如下：

設(shè)一個重復(fù)操作的閥值S,令S=3N；

int S=3N；

IA=1；//給數(shù)組An位置指示賦初值

IB=1；//給數(shù)組An位置指示賦初值,讓其指在位置1處

srand（（unsigned）time（NULL））；//給隨機(jī)函數(shù)設(shè)定種子

for（int d=0；d＜S；d++）//重復(fù)最多S次循環(huán)

{

R=rand（）%（N+1）；//產(chǎn)生一個值[1,N]的隨機(jī)數(shù) R

If（An[R]==0）//判斷數(shù)組下標(biāo)為R的元素的值是否為零,如果是則繼續(xù)

{

An[R]=R；//將A n[R]的下標(biāo)值賦給它,這就是所謂的下標(biāo)填充

Bm[IB]=R；//并且把R值依次放到數(shù)組B m中

IB++；//把數(shù)組B m的元素位置指示加1；

if（IB＞M）{break；}//如果己產(chǎn)生M個隨機(jī)數(shù)則跳出,否則繼續(xù)

}

}

上面這段代碼就是最多以S次循環(huán)來生成所要求的隨機(jī)數(shù),令S=3N的原因為rand（）返回值是均勻分布的,因此S=3N次將基本使其返回值遍布在[0,N]區(qū)間上.

通過下標(biāo)填充的方式產(chǎn)生一個隨機(jī)數(shù)R,判斷隨機(jī)數(shù)R是否己經(jīng)被采納.如果尚未被采納,則將隨機(jī)數(shù)R保存起來,并把A n[R]值設(shè)為R.通過這種方法來保證獲得不重復(fù)的隨機(jī)數(shù)[6].例如先產(chǎn)生第一個隨機(jī)數(shù)6.便令A(yù) n[6]=6,并令B m中還沒有賦值的第一個元素的值為6.第二個產(chǎn)生的隨機(jī)數(shù)是3,同樣就有A n[3]=3,B m[2]=3.以此類推,直到產(chǎn)生足夠數(shù)量的隨機(jī)數(shù).

3 用補(bǔ)尾法補(bǔ)充剩下的隨機(jī)數(shù)

一般情況下M次循環(huán)就可以產(chǎn)生大多數(shù)符合要求的隨機(jī)數(shù).但是rand（）%（N+1）畢竟只是一個隨機(jī)的結(jié)果,當(dāng)N比較大,而M又和N比較接近時,從概率上來講,生成M個隨機(jī)數(shù)時間就會增加許多,因為要循環(huán)更多次數(shù)才行.而這樣做效率太低,因為需要產(chǎn)生的隨機(jī)數(shù)個數(shù)已經(jīng)很有限了,因此就可以使用補(bǔ)尾法來解決這個問題.由于沒有產(chǎn)生足夠數(shù)量符合求隨機(jī)數(shù),數(shù)組B m的后幾位元素還沒有賦值.掃描A n數(shù)組,順序隨意,這里從前往后掃描.當(dāng)發(fā)現(xiàn)有元素A n[IA]位置的值為零時,即令A(yù)[IA]=IA,同時將IA賦給B m尚未賦值的元素,重復(fù)操作直到B m被填滿為止.這就是補(bǔ)尾法.即把B m中尚未賦值的尾巴,依次補(bǔ)上A n中尚未被填充元素的下標(biāo)值.通過使用補(bǔ)尾法,可以有效地縮短循環(huán)次數(shù),并可杜絕死循環(huán)產(chǎn)生的情形.

下面給出補(bǔ)尾的算法的代碼：

if（IB＜M）

{

for（IA=1；IA＜=N；IA++）

{

if（An[IA]==0）

{Bm[IB]=i；

if（IB＞=M）{break；}

IB++；

}

}

把下標(biāo)填充生成部分和后面的補(bǔ)尾生成部分結(jié)合起來,就成了“下標(biāo)填充補(bǔ)尾法”.

4 算法效率驗證

4.1 實驗環(huán)境

Windows XP,C++Builder 6.0.

4.2 實驗方法

在[1,10 000]區(qū)間上,產(chǎn)生M個隨機(jī)數(shù),按照通常方法和下標(biāo)填充補(bǔ)尾法執(zhí)行,重復(fù)3次.

4.3 實驗結(jié)果和分析

實驗結(jié)果見表1.

表1 不同算法的循環(huán)次數(shù)

由表1可知,對比于通常方法,在M值很大時,下標(biāo)填充補(bǔ)尾法的效率有明顯改善.由于S的閥值作用,使生成供挑選隨機(jī)數(shù)的循環(huán)次數(shù)大幅度減小.而當(dāng)M較小時和通常方法的循環(huán)次數(shù)相當(dāng),這一點(diǎn)保證了在M較小時生在隨機(jī)數(shù)的有充分的隨機(jī)性.

5 算法應(yīng)用

利用下標(biāo)填充補(bǔ)尾法,保證了無重復(fù)隨機(jī)數(shù)的高效產(chǎn)生.下面通過實例驗證了這種算法在實踐中的典型應(yīng)用.

應(yīng)用一：從有N道試題的題庫中,隨機(jī)生成擁有M道試題的試卷.如果M＜N,則生成試卷.如果M≥N,則直接把所有的試題全選即可.全選時,沒有考虙排序的問題.但有些應(yīng)用卻要求打亂順序,這時可以用下標(biāo)填充補(bǔ)尾法生成所要的隨機(jī)序列.

應(yīng)用二：發(fā)牌問題,即如何把撲克牌以高效的方法隨機(jī)派發(fā).現(xiàn)在以52張牌分發(fā)給甲、乙、丙、丁4個人為例,這就相當(dāng)于把52個數(shù)進(jìn)行隨機(jī)分配

令 N=52,M=39；（52-52/4=39）；則有數(shù)組 A52,B39

當(dāng)產(chǎn)生了39個隨機(jī)數(shù)后,數(shù)組B39己經(jīng)填滿了,這時數(shù)組A52里還有13個元素沒有被選中,把這13個元素全部給“丁”；再把數(shù)組B39中的元素平分成三段,依次派給“甲”、“乙”、和“丙”.問題解決.

應(yīng)用三：學(xué)生分班問題,新生入學(xué)時,涉及到隨機(jī)分班.為了使各班級相對平衡,這要要求分班時能真正的隨機(jī).如有300人入學(xué),需要分到10個班.這就相當(dāng)于把300個數(shù)隨機(jī)分配.令N=300,M=270；計算方法同上.

6 結(jié)論

本文探討了一種新的一定范圍內(nèi)的無重復(fù)隨機(jī)數(shù)的產(chǎn)生算法——下標(biāo)填充補(bǔ)尾法.這種算法具有高效和可靠的特點(diǎn),提高了生成速度并有效地避免了死循環(huán)的產(chǎn)生.實驗證明,產(chǎn)生規(guī)定范圍內(nèi)無重復(fù)的隨機(jī)數(shù),使用這種算法與通常方法相比較,隨機(jī)數(shù)數(shù)量越接近區(qū)間值,效率提升越明顯.

[1]Hellekalek P.Good random number generators are（not so）easy to find[J].Mathematics and Computers in Simulation,1998,46（5/6）：485-505.

[2]Gonzalez J A,Pino R.A random number generator based on unpredictable chaotic functions[J].Computer Physics Communications,1999,120：109-114.

[3]Pang W K,Yang Z H,Hou S H.The vertical strip method for generation of random number with given density[J].European Journal ofOperation Research,2002,142（3）：5952609.

[4]Fang K T,Yang Z H,Samuel K.Generation ofmultivariate distribut ions by vertical density rep resentat ion[J].Stat ist ics,2001,35：2812293.

[5]Bailey R W.Polar generation of random variates with the distribution[J].Mathematics ofComputation,1994,62：7792781.

[6]楊自強(qiáng),魏公毅.產(chǎn)生偽隨機(jī)數(shù)的若干新方法[J].數(shù)值計算與計算機(jī)應(yīng)用,2001,22（3）：202-216.