学步园

   注意,下面均以在101~200的范围内(设为b[100],它实际上是附加空间),从中产生10个不重复的随机数(设为a[10]).
  
一.牺牲时间为代价
   这种方法不需要附加空间b数组.
   要产生一定范围内不可重复的随机数，把曾经生成的随机数保存起来作为历史数据。产生一个新的随机数后在历史数据搜索，若找到就重新产生一个新的再重复数据搜索；否则就认为已经找到了一个新的不同随机数。
   可以预见,每个新产生的随机数都要与前面所有的数比较.若重复,舍弃,再产生;否则,产生下一个.平均耗时n的平方量级.
   粗看起来，上面的程序似乎没有什么问题，在执行过程中程序也能够通过。但，仔细分析我们就会发现问题出在一个新产生的随机数是否已经存在的判定上。既然是随机数，那么从数学的角度来说在概率上，每次产生的随机数 r就有可能相同，尽管这种可能性很小，但确是一个逻辑性与正确性的问题。因此，每次产生的新的随机数r都有可能是数组random的前i-1个数中的某一个，也就是说程序在运行过程中由此可能会导致死循环!
    有人可能会争辩说,这种概率很小嘛,几乎为零.的确,但我要问,算法的五大特性是什么,其中两大特性就是:确定性和有穷性.
    所以,怎么解决?牺牲空间.(稍后介绍)

二.牺牲空间为代价
   以下方法需要附加空间b数组.
   (1)将范围数组b[100](b[i]=100+i,不妨设数组下标从1开始)的每个元素设置一个标志位flag.初始均为flag=0;若某元素被选入到a数组中,则flag=1;显然,以后再选到重复元素可以立刻判定是否已选.这不正是以空间换时间吗?
   但是仍然有一个很严重的问题,在小规模输入下,无疑它的表现是不错的.但现在举一个失败的例子.
   在1~65536之间,选择65500个不重复的随机数.看看后面的随机数,比如第65500个数(最后一个),它要在剩下的36个数中选择才会有flag=0(根本不知道这36个数是什么);哼哼,概率36/65536.越到后面,随机数越难产生,空间也换不了时间.
   改进:先在1~65536之间随机选取36个数,删除.将剩下的65500个数依次赋值给a[65500],然后打乱顺序即可,如下伪码:

1 for  i ← 
1  to length[a]
2    
do  j ← random() 
// 随机产生一个a数组的下标

3
      exchange a[i]←→a[j]
// 交换a[i]与a[j]
4

  当范围数组与目标数组的大小非常接近时,上述算法非常有效,建议采用.

  (2)问题的最终解决.
   仍以最开始的那个例子来说,初始数组b[i]=100+i,a数组空.
   每次随机生成数组b的一个下标subscript，然后取出它所对应的数据a[subscript],记下来.然后将数组b的最后一个数b[length]放到下标subscript的位置，同时将数组a长度减1。尽管前若干次生成的下标subscript随机数有可能相同，但，因为每一次都把最后一个数填到取出的位置，因此，相同下标subscript对应的数却绝不会相同，每一次取出的数都不会一样，这样，就保证了算法的确定性、有效性、有穷性.
  伪码算法如下:

 1 lower ←  101

 2
upper ← 
200
 3
for  i ← 
1  to upper
- lower
+ 1
 4
    
do  b[i]
= lower +
i -
1
 5
for  i←
1  to length[a]
 6     
do  subscript 
=  (
int )(length[b]
* Rnd  +
 lower) //
随机产生b数组的一个下标,Rnd产生0~1随机数
 7
       temp ← b[subscript]
 8        b[subscript] ← b[length[b]]
 9        length[b]
-- ;
10        a[i]
= temp;
11