规定范围内一定数量无重复随机数的产生算法及应用

谢春祥,张兆亮

（蚌埠学院,安徽蚌埠233030）

规定范围内一定数量的随机数的产生在生产研究中有着广泛的应用.通常的随机数产生方法是重复进行生成操作,直到产生足够数量的随机数为止.并且为了防止重复,还要不断扫描对比己经生成的随机数.这样效率很低,而且可能陷入死循环（一直产生不了合格的随机数,程序持续空转）[1-6].本文提出通过“下标填充补尾法”,可以有效解决通常方法的弊端,达到高效可靠的目的.

1 通常产生规定范围随机数的方法

要生成符合要求的随机数,通常都是先产生一般的随机数,再通过特定的方法从中挑选所需要的数.普通随机数的产生常用的rand（）函数实现,例如,要生成一个值在区间[1,N]内的随机数R,代码如下：

srand（（unsigned）time（NULL））；

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

第1行代码是给随机数函数赋一个种子值,以便随机函数在此基础上递推出随机数来.这里用不断变化的计算机时间做种子.在第2行代码里,由rand（）函数产生一个随机数.但由于rand（）的返回值在0～327 67之中（一个short整型数值的范围）,所以当N值小于327 67时,就要将返回值模（N+1）取余,以使值的范围一定落在[1,N]中.如果要取的随机数值大于327 67,则可由多个rand（）的返回值进行线性叠加获得[2].一定范围内随机数产生了,下面着重探讨如何产生规定数量的随机数.

2 下标填充法产生随机数

假设要产生M个值在区间[1,N]的随机数.常用的方法就是重复执行上面所说的两行代码,直到产生M个满足条件的随机数为止[3-5].但这样做将要花费大量的时间,尤其是当M和N很接近时,而且难以满足无重复的要求.所以必须找一个新的高效数法,从根本上解决这个问题.这就是下标填充补尾法.

先定义一个长度N的一维数组,名为A n,将初值全设为0,数组下面的格子中显示的是他们的下标；再定义一个长度为M的一维数组B m.

数组A n（注意：是一维数组,下一行是每个元素的位置）

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

数组B m

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

算法代码如下：

设一个重复操作的阀值S,令S=3N；

int S=3N；

IA=1；//给数组An位置指示赋初值

IB=1；//给数组An位置指示赋初值,让其指在位置1处

srand（（unsigned）time（NULL））；//给随机函数设定种子

for（int d=0；d＜S；d++）//重复最多S次循环

{

R=rand（）%（N+1）；//产生一个值[1,N]的随机数 R

If（An[R]==0）//判断数组下标为R的元素的值是否为零,如果是则继续

{

An[R]=R；//将A n[R]的下标值赋给它,这就是所谓的下标填充

Bm[IB]=R；//并且把R值依次放到数组B m中

IB++；//把数组B m的元素位置指示加1；

if（IB＞M）{break；}//如果己产生M个随机数则跳出,否则继续

}

}

上面这段代码就是最多以S次循环来生成所要求的随机数,令S=3N的原因为rand（）返回值是均匀分布的,因此S=3N次将基本使其返回值遍布在[0,N]区间上.

通过下标填充的方式产生一个随机数R,判断随机数R是否己经被采纳.如果尚未被采纳,则将随机数R保存起来,并把A n[R]值设为R.通过这种方法来保证获得不重复的随机数[6].例如先产生第一个随机数6.便令A n[6]=6,并令B m中还没有赋值的第一个元素的值为6.第二个产生的随机数是3,同样就有A n[3]=3,B m[2]=3.以此类推,直到产生足够数量的随机数.

3 用补尾法补充剩下的随机数

一般情况下M次循环就可以产生大多数符合要求的随机数.但是rand（）%（N+1）毕竟只是一个随机的结果,当N比较大,而M又和N比较接近时,从概率上来讲,生成M个随机数时间就会增加许多,因为要循环更多次数才行.而这样做效率太低,因为需要产生的随机数个数已经很有限了,因此就可以使用补尾法来解决这个问题.由于没有产生足够数量符合求随机数,数组B m的后几位元素还没有赋值.扫描A n数组,顺序随意,这里从前往后扫描.当发现有元素A n[IA]位置的值为零时,即令A[IA]=IA,同时将IA赋给B m尚未赋值的元素,重复操作直到B m被填满为止.这就是补尾法.即把B m中尚未赋值的尾巴,依次补上A n中尚未被填充元素的下标值.通过使用补尾法,可以有效地缩短循环次数,并可杜绝死循环产生的情形.

下面给出补尾的算法的代码：

if（IB＜M）

{

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

{

if（An[IA]==0）

{Bm[IB]=i；

if（IB＞=M）{break；}

IB++；

}

}

把下标填充生成部分和后面的补尾生成部分结合起来,就成了“下标填充补尾法”.

4 算法效率验证

4.1 实验环境

Windows XP,C++Builder 6.0.

4.2 实验方法

在[1,10 000]区间上,产生M个随机数,按照通常方法和下标填充补尾法执行,重复3次.

4.3 实验结果和分析

实验结果见表1.

表1 不同算法的循环次数

由表1可知,对比于通常方法,在M值很大时,下标填充补尾法的效率有明显改善.由于S的阀值作用,使生成供挑选随机数的循环次数大幅度减小.而当M较小时和通常方法的循环次数相当,这一点保证了在M较小时生在随机数的有充分的随机性.

5 算法应用

利用下标填充补尾法,保证了无重复随机数的高效产生.下面通过实例验证了这种算法在实践中的典型应用.

应用一：从有N道试题的题库中,随机生成拥有M道试题的试卷.如果M＜N,则生成试卷.如果M≥N,则直接把所有的试题全选即可.全选时,没有考虙排序的问题.但有些应用却要求打乱顺序,这时可以用下标填充补尾法生成所要的随机序列.

应用二：发牌问题,即如何把扑克牌以高效的方法随机派发.现在以52张牌分发给甲、乙、丙、丁4个人为例,这就相当于把52个数进行随机分配

令 N=52,M=39；（52-52/4=39）；则有数组 A52,B39

当产生了39个随机数后,数组B39己经填满了,这时数组A52里还有13个元素没有被选中,把这13个元素全部给“丁”；再把数组B39中的元素平分成三段,依次派给“甲”、“乙”、和“丙”.问题解决.

应用三：学生分班问题,新生入学时,涉及到随机分班.为了使各班级相对平衡,这要要求分班时能真正的随机.如有300人入学,需要分到10个班.这就相当于把300个数随机分配.令N=300,M=270；计算方法同上.

6 结论

本文探讨了一种新的一定范围内的无重复随机数的产生算法——下标填充补尾法.这种算法具有高效和可靠的特点,提高了生成速度并有效地避免了死循环的产生.实验证明,产生规定范围内无重复的随机数,使用这种算法与通常方法相比较,随机数数量越接近区间值,效率提升越明显.

[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]杨自强,魏公毅.产生伪随机数的若干新方法[J].数值计算与计算机应用,2001,22（3）：202-216.