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

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

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

下面均以在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 
  
  	
通过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 
  
  	
这个方法减少了一层循环嵌套，效率上有一定的改善。
    
    
通过随机排序来实现
  
  	
这种方法彻底的颠覆了方法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
  
  	
如果所要生成的随机数比较少的话，可以将所有的先存到数组当中，然后再随机交换数组当中的数字即可：
    
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，欢迎访问原出处。