生成不重复的随机数的思路

总结这类问题的各种方法
服务器君一共花费了230.921 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

通常的生成随机数的做法是不考虑重复的,因为即使重复也属于概率意义上的正常情况。但某些情况下需要不重复的随机数据,怎么办呢?

我想从大方向上来说,应该只有两个方法。要么牺牲时间要么牺牲空间。

下面均以在101~200的范围内(设为b[100],它实际上是附加空间),从中产生10个不重复的随机数(设为a[10])。

牺牲时间为代价

这种方法不需要附加空间b数组。

要产生一定范围内不可重复的随机数,把曾经生成的随机数保存起来作为历史数据。产生一个新的随机数后在历史数据搜索,若找到就重新产生一个新的再重复数据搜索;否则就认为已经找到了一个新的不同随机数。

可以预见,每个新产生的随机数都要与前面所有的数比较。若重复,舍弃,再产生;否则,产生下一个。平均耗时n的平方量级。

粗看起来,上面的程序似乎没有什么问题,在执行过程中程序也能够通过。但,仔细分析我们就会发现问题出在一个新产生的随机数是否已经存在的判定上。既然是随机数,那么从数学的角度来说在概率上,每次产生的随机数 r就有可能相同,尽管这种可能性很小,但确是一个逻辑性与正确性的问题。因此,每次产生的新的随机数r都有可能是数组random的前i-1个数中的某一个,也就是说程序在运行过程中由此可能会导致死循环!

有人可能会争辩说,这种概率很小嘛,几乎为零。的确,但我要问,算法的五大特性是什么,其中两大特性就是:确定性和有穷性。

所以,怎么解决?牺牲空间。

牺牲空间为代价

以下方法需要附加空间b数组。

将范围数组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],然后打乱顺序即可。

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

仍以最开始的那个例子来说,初始数组b[i]=100+i,a数组空。

每次随机生成数组b的一个下标subscript,然后取出它所对应的数据a[subscript],记下来。然后将数组b的最后一个数b[length]放到下标subscript的位置,同时将数组a长度减1。尽管前若干次生成的下标subscript随机数有可能相同,但,因为每一次都把最后一个数填到取出的位置,因此,相同下标subscript对应的数却绝不会相同,每一次取出的数都不会一样,这样,就保证了算法的确定性、有效性、有穷性。

以生成1-10之间的10个不重复的随机数为例,介绍生成不重复的随机数的一些方法。

通过while循环来实现

通过while循环不停的生成随机数,直到生成一个不重复的为止,这种方法比较容易想到,但是效率也比较低下,实例代码如下:

static void Main(string[] args)
{
	int[] result = new int[10];
	int tmp = -1;
	Random random = new Random();
	bool repeat = false;
	for (int i = 0; i < 10; i++)
	{
  		repeat = true;
 		while (repeat)
       	{
     		repeat = false;
        	tmp = random.Next(1, 11);
         	for (int j = 0; j < i; j++)
           	{
           		if (tmp == result[j])
            	{
                	repeat = true;
                 	break;
          		}
     		}
		}
		result[i] = tmp;
   	}
	for (int i = 0; i < 10; i++)
		Console.WriteLine(result[i].ToString());                
}

通过for循环来实现

方法1使用了多处循环嵌套,效率十分低下,所以我应用一定的技巧来减少循环嵌套,来达到提高程序效率的目的。主要思路是如果检测到重复,就把循环变量减1,这样来重新进行一次循环,重新生成一个随机数,直到生成一个不重复的随机数为止,实例代码如下:

static void Main(string[] args)
{
	int[] result = new int[10];
	int tmp = -1;
	Random random = new Random();
	bool repeat = false;
	for (int i = 0; i < 10; i++)
	{
  		repeat = false;
    	tmp = random.Next(1, 11);
    	for (int j = 0; j < i; j++)
     	{
          	if (tmp == result[j])
         	{
         		repeat = true;
              	break;
   			}
     	}
     	if (!repeat)
   		{
       		result[i] = tmp;
    	}
     	else
      	{
         	i = i - 1;//循环变量-1
    	}
                
	}
	for (int i = 0; i < 10; i++)
		Console.WriteLine(result[i].ToString());  
}

这个方法减少了一层循环嵌套,效率上有一定的改善。

通过随机排序来实现

这种方法彻底的颠覆了方法1和2的基本思路,先初始化一个包含数字1-10的数组,然后每次循环取一个随机位置,将这个位置的元素和最后一个位置的元素交换!实例代码如下:

static void Main(string[] args)
{
	int[] result = new int[10];
	for (int i = 0; i < 10; i++)
   		result[i] = i + 1;
	for (int j = 9; j > 0; j--)
  	{
    	Random r = new Random();
   		int index = r.Next(0, j);
     	int temp = result[index];
    	result[index] = result[j];
     	result[j] = temp;
	}
 	for (int i = 0; i < 10; i++)
		Console.WriteLine(result[i].ToString());
}

这种方法消除了循环嵌套,效率上获得了进一步的改善,但是也有一定的限制,如果要生成5组1-10之间的随机数,那这种打乱顺序的方法就无法使用了。

总结

  • 方法1效率比较低下,一般不推荐使用。
  • 方法2比较通用,效率高于方法1,但是效率低于方法3。
  • 方法3虽然效率比较高,但是只能应用与特定的情况下。

下面的例子的主要是思路是,如果检测到已经存在该数字,则将循环数后退一个,重新生成。

void static Main()
{
  Random random = new Random();
  bool repeat = true;
  int temp ;
  int[] store = new int[10];
  for(int i = 0;i < 10;i++)
  {
    temp =random.Next(1,11);
    for(int j = 0; j<i;j++)
    {
      repeat = false ;
      if(temp == store[j])
      {
        repeat = true;
        break;
      }
    }
    store[i] = temp;    //将不重复的值存储到定义的数组当中
  }
  for(int  i = 0;i < 10;i++)
  {
    Console.WriteLine("store[{0}]为:{1}",i,store[i]);
  }
}

如果所要生成的随机数比较少的话,可以将所有的先存到数组当中,然后再随机交换数组当中的数字即可:

static void Main()
{ 
  int[] store = new store[10];  //定义一个数组,并初始化
  for(int i =1;i<11;i++)      //通过循环将数组进行赋值
  {
    store[i-1] = i;
  }
 
  for(int j = 9;j>0;j--)
  {
    Random r = new Random();
    int index = r.Next(0,j);    //int index = r.Next(0,9);  这个值得商榷,感觉有些问题。
    int temp = store[index]; 
    store[index] = store[j];
    store[j] = temp;
  }
}

本文地址:http://www.nowamagic.net/librarys/veda/detail/510,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/510

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《深入理解MySQL核心技术》 Sasba Pacbev (作者), 李芳 (译者), 于红芸 (译者), 邵健 (译者)

《深入理解MySQL核心技术》:从公共可用性的意义上讲,MySQL源代码是开放源代码,但如果对其不了解,则实质上,它对于您来说是封闭的。MysQL开发团队的前成员Sasha Pachev通过《深入理解MySQL核心技术》给出了MySQL 5的全面指南,揭示了这一强大数据库的内部运作。您将直奔MySQL核心技术,了解各种数据结构和各种方便的功能的运作情况,了解如何添加新的存储引擎和配置选项等。 《深入理解MySQL核心技术》从结构概况讲起,在这一部分解释了MysQL的不同组件是如何协同工作的。接着将学习设置有效的可编译代码副本的步骤,然后使用基本架构添加自己的配置变量和存储引擎。

更多计算机宝库...