如何高效产生m个n范围内的不重复随机数（m<=n)

浅浅的花香味﹌ 2022-08-06 05:10 171阅读 0赞

如何产生不重复的随机数？最容易想到的方法，是逐个产生这些随机数，每产生一个，都跟前面的随机 数比较如果重复，就重新产生。这是个很笨的方法，且比较次数呈线性增长，越往后次数越多。其实这些 比较是多余的，完全可以不进行比较，只要反过来，按顺序产生这些数，但随机产生它们的位置。例如下 面产生100个100以内不重复随机数的代码：

int a\[100\];  
for(i=0; i<=99; ++i) a\[i\]=i;  
for(i=99; i>=1; --i) swap(a\[i\], a\[rand()%i\]);  
上面这段代码只需要遍历一次就可以产生这100个不重复的随机数，它是如何做到的呢？首先第二行按顺  
序用0到99填满整个数组；第三行，是随机产生从0到m-2个数组下标，把这个下标的元素值跟m-1下标的元  
素值交换，一直进行到下标为1的元素。因此它只需要遍历一次就能产生全部的随机数。  
        再看下面的代码，原理跟上面例子相似，但效率比上面的差点，但仍不失为一个好方法：  
int a\[100\]=\{0\};  
int i, m;  
for(i=1; i<=99; ++i)  
\{  
        while(a\[m=rand()%100\]);  
        a\[m\] = i;  
\}  
这段代码也是随机产生位置，但它预先把整个数组初始化为0，然后随机产生其中一个位置，如果该元素  
值为0，表示这个位置还没有被使用过，就把i赋予它；否则，就重新随机产生另一个位置，直到整个数组  
被填满。这个方法，越到后面，遇到已使用过的元素的可能性越高，重复次数就越多，这是不及第一个方  
法的地方，但总的来说，效率还是不错的。  
===================================================================================  
1.产生一个随机数(从0到32767)  
   srand((unsigned) time(NULL)); //为了提高不重复的概率  
   rand(); //产生随机数  
2.产生从m到n的随机数(包括m,不包括n)  
   srand((unsigned) time(NULL)); //为了提高不重复的概率  
   rand()%(n - m + 1) + m;                //使用时将m和n换为具体数即可  
==================================================================================  
问题的来由 - "随机取m个数（在1到n的范围之内），（m <= n)，要求m个数没有重复。有没有  
什么好的算法，时间复杂度和空间复杂度都很好"  
\----------------------------------------------------------------  
方案一:  
取随机数可以用C++标准的rand，至于M个不重复，你可以用std::set来解决，把取道的随机数  
插入到set里面，set的size() == m就可以了, 具体可以这样:  
\#include <set>  
\#include <stdlib.h>  
int main()  
\{  
   std::set<int> s;  
   while(1)  
   \{  
      int r = rand() % n;  
      s.insert(r);  
      if(s.size() == m)  
      \{  
         break;  
      \}  
   \}  
\}  
由于set底层实现是红黑树，插入复杂度是对数级的^\_^  
\----------------------------------------------------------------  
方案二:  
\#include <iostream>  
\#include <cstdlib>      //用于rand()和srand()函数  
\#include <ctime>        //设置不同的随机数  
using namespace std;  
int main ()\{  
    srand( time( 0 ) );    //调用不重复的随机数函数  
    unsigned i;  
    for ( int n = 0; n++ < 10; )  
    \{  
        i = rand() ;        //对i 赋系统的随机数  
        cout << " The NO." << n << "is : " << i << endl;  
    \}  
    return 0;  
\}  
1. C++标准函数库提供一随机数生成器rand，返回0－RAND\_MAX之间均匀分布的伪随机整数。 RAND\_MAX  
   必须至少为32767。rand()函数不接受参数，默认以1为种子（即起始值）。  
   随机数生成器总是以相同的种子开始，所以形成的伪随机数列也相同。失去了随机意义。  
2. C++中另一函数srand（），可以指定不同的数（无符号整数变元）为种子。但是如果种子相同，伪  
   随机数列也相同。－－一个办法是让用户输入种子，但是仍然不理想。  
  
  
3. 比较理想的是用变化的数，比如时间来作为随机数生成器的种子。  
   在 头文件ctime中时间库包含time函数，它可以返回一个表示时间、日期、月和年的数值使用如  
   下调用可将该值设为rand的种子  
   srand(static\_cast<unsigned>(time(static\_cast<time\_t\*>(NULL))));  
4. 但, srand()并不是说使随机数都不一样,它只是使取随机数的种子随着时间而改变:)  
   So, 还是方案一好!  
===============================================================================  
生成无重复的随机数,注意,是不重复的序列.  
   通常的生成随机数的做法是不考虑重复的,因为即使重复也属于概率意义上的正常情况.但某些情况下需要不重复的随机数据,怎么办呢?  
   我想从大方向上来说,应该只有两个方法.要么牺牲时间要么牺牲空间.讲得不对或不完整,大家一定要指出来啊,谢谢.  
   
                            =---------------来源CSDN  
   
   注意,下面均以在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 如何高效产生m个n范围内的不重复随机数（m<=n) for i ← 1 to length\[a\]  
2 如何高效产生m个n范围内的不重复随机数（m<=n)    do j ← random() // 随机产生一个a数组的下标   
3 如何高效产生m个n范围内的不重复随机数（m<=n)        exchange a\[i\]←→a\[j\] // 交换a\[i\]与a\[j\]  
4 如何高效产生m个n范围内的不重复随机数（m<=n)  
当范围数组与目标数组的大小非常接近时,上述算法非常有效,建议采用.  
(2)问题的最终解决.  
   仍以最开始的那个例子来说,初始数组b\[i\]=100+i,a数组空.  
   每次随机生成数组b的一个下标subscript，然后取出它所对应的数据a\[subscript\],记下来.然后将数组b的最后一个数b\[length\]放到下标subscript的位置，同时将数组a长度减1。尽管前若干次生成的下标subscript随机数有可能相同，但，因为每一次都把最后一个数填到取出的位置，因此，相同下标subscript对应的数却绝不会相同，每一次取出的数都不会一样，这样，就保证了算法的确定性、有效性、有穷性.  
伪码算法如下:  
lower ← 101   
upper ← 200   
for i ← 1 to upper - lower + 1   
 do b\[i\] = lower + i - 1   
for i← 1 to length\[a\]  
   do subscript = ( int )(length\[b\] \* Rnd + lower) // 随机产生b数组的一个下标,Rnd产生0~1随机数   
        temp ← b\[subscript\]  
       b\[subscript\] ← b\[length\[b\]\]  
      length\[b\] -- ;  
        a\[i\] = temp;