c#随机产生不重复数组

  1. 云栖社区>
  2. 博客列表>
  3. 正文

c#随机产生不重复数组

awbeci 2011-04-14 13:37:00 浏览166 评论0

摘要: 在.NET技术 C#区看到一个小问题:从1,50随机20个不重复数。 问题不复杂,提问者其实已经有了自己的答案,但他似乎觉得答案不太理想。 ArrayList list =new ArrayList();int k =0;do{k =random .Next (1,51);if (!list.Contains(k))list.Add(k);}while (list.Count 32));   这样可以保证99%不是一样。

在.NET技术 C#区看到一个小问题:从1,50随机20个不重复数。

问题不复杂,提问者其实已经有了自己的答案,但他似乎觉得答案不太理想。

ArrayList list =new ArrayList();
int k =0;
do
{
k
=random .Next (1,51);
if (!list.Contains(k))
list.Add(k);
}

while (list.Count <20);


这种方法应该说比较常规,效率也算不差了。但有没有更好的方法呢?换个思路想一想就有了下面这个方法。

此方法经测试性能会有所提高,尤其是结果较大时。


publicint[] GetRandomUnrepeatArray(int minValue, int maxValue, int count)
{
Random rnd
=new Random();
int length = maxValue - minValue +1;
byte[] keys =newbyte[length];
rnd.NextBytes(keys);
int[] items =newint[length];
for (int i =0; i < length; i++)
{
items[i]
= i + minValue;
}

Array.Sort(keys, items);
int[] result =newint[count];
Array.Copy(items, result, count);
return result;
}


和常规思路不同,不是采取先获取一个随机数查找有无重复之后加入结果集,而是先利用 Random.NextBytes 方法得到一个随机数字节数组,然后利用 Array.Sort 的重载方法用这个随机数字节数组顺序数组排序为乱序,最后 Copy 出结果集。

由于只用了一个循环来为顺序源数组赋初值,只使用了简单数组类型而没有用集合或泛型集合类,利用 Random.NextBytes 方法一次获得一组随机数而不是在循环中多次调用,Array.Copy 方法复制结果集。因而性能得到优化。

这里要注意Random.NextBytes 方法获得的数组是字节数组,其长度大于 256 时必定是有重复的,但 Array.Sort 方法的 QuickSort 算法刚好是不稳定排序,这样我们得到的排序结果刚好符合要求。

另外这里的随机数仅作为排序用,所以这个方法只需要改动返回类型和
源数组赋初值的操作就可以输出任何简单数据类型的随机不重复数组。

其实这个例子如果用C++或别的什么语言来实现我们可以有更多的优化考虑,但.NET的优点在于让我们可以摆脱那些头痛的算法而更多的关注业务。

最后,如果不考虑性能用泛型类尤其是排序泛型类来写代码可以更简练。

我们在做能自动生成试卷的考试系统时,常常需要随机生成一组不重复的题目,在.net Framework中提供了一个专门用来产生随机数的类System.Random。

  对于随机数,大家都知道,计算机不可能产生完全随机的数字,所谓的随机数发生器都是通过一定的算法对事先选定的随机种子做复杂的运算,用产生的结果来近似的模拟完全随机数, 这种随机数被称作伪随机数。伪随机数是以相同的概率从一组有限的数字中选取的。所选数字并不具有完全的随机性,但是从实用的角度而言,其随机程度已足够 了。伪随机数的选择是从随机种子开始的,所以为了保证每次得到的伪随机数都足够地“随机”,随机种子的选择就显得非常重要。如果随机种子一样,那么同一个 随机数发生器产生的随机数也会一样。一般地,我们使用同系统时间有关的参数作为随机种子,这也是.net Framework中的随机数发生器默认采用的方法。

  我们可以使用两种方式初始化一个随机数发生器:

  第一种方法不指定随机种子,系统自动选取当前时间作为随机种子:

  Random ro = new Random();

  第二种方法可以指定一个int型参数作为随机种子:
  int iSeed=10;
  Random ro = new Random(10);

  long tick = DateTime.Now.Ticks;
  Random ran = new Random((int)(tick & 0xffffffffL) | (int) (tick >> 32));
  这样可以保证99%不是一样。

  之后,我们就可以使用这个Random类的对象来产生随机数,这时候要用到Random.Next()方法。这个方法使用相当灵活,你甚至可以指定产生的随机数的上下限。

  不指定上下限的使用如下:
  int iResult;
  iResult=ro.Next();

  下面的代码指定返回小于100的随机数:

  int iResult;
  int iUp=100;
  iResult=ro.Next(iUp);

  而下面这段代码则指定返回值必须在50-100的范围之内:
  int iResult;
  int iUp=100;
  int iDown=50;
  iResult=ro.Next(iDown,iUp);

  除了Random.Next()方法之外,Random类还提供了Random.NextDouble()方法产生一个范围在0.0-1.0之间的随机的双精度浮点数:
  double dResult;
  dResult=ro.NextDouble();

  但是用Random类生成题号,会出现重复,特别是在数量较小的题目中要生成不重复的的题目是很难的,参考了网上的一些方法,包括两类,一类是通过随机种子入手,使每一次的随机种子不同,来保证不重复;第二类是使用一些数据结构和算法。下面主要就第二类介绍几个方法。

  方法1:思想是用一个数组来保存索引号,先随机生成一个数组位置,然后把这个位置的索引号取出来,并把最后一 个索引号复制到当前的数组位置,然后使随机数的上限减一,具体如:先把这100个数放在一个数组内,每次随机取一个位置(第一次是1-100,第二次是 1-99,...),将该位置的数用最后的数代替。


  int[] index = new int[15];
  for (int i = 0; i < 15; i++)
    index = i;
 
 Random r = new Random();
  //用来保存随机生成的不重复的10个数
  int[] result = new int[10];
  int site = 15;//设置下限
  int id;
  for (int j = 0; j < 10; j++)
  {
    id = r.Next(1, site - 1);
    //在随机位置取出一个数,保存到结果数组
    result[j] = index[id];
    //最后一个数复制到当前位置
    index[id] = index[site - 1];
    //位置的下限减少一

    site--;
  }

  方法2:利用Hashtable。
  Hashtable hashtable = new Hashtable();
  Random rm = new Random();
  int RmNum = 10;
  for (int i = 0; hashtable.Count < RmNum; i++)
  {
   int nValue = rm.Next(100);
   if (!hashtable.ContainsValue(nValue) && nValue != 0)
   {
   hashtable.Add(nValue, nValue);
   Console.WriteLine(nValue.ToString());
   }
  }

  方法3:递归,用它来检测生成的随机数是否有重复,如果取出来的数字和已取得的数字有重复就重新随机获取。
  Random ra=new Random(unchecked((int)DateTime.Now.Ticks));
  int[] arrNum=new int[10];
  int tmp=0;
  int minValue=1;
  int maxValue=10;
  for (int i=0;i<10;i++)
  {
    tmp=ra.Next(minValue,maxValue); //随机取数
    arrNum=getNum(arrNum,tmp,minValue,maxValue,ra); //取出值赋到数组中
  }
  .........
  .........
  public int getNum(int[] arrNum,int tmp,int minValue,int maxValue,Random ra)
  {
    int n=0;
    while (n<=arrNum.Length-1)
    {
      if (arrNum[n]==tmp) //利用循环判断是否有重复
      {
        tmp=ra.Next(minValue,maxValue); //重新随机获取。

        getNum(arrNum,tmp,minValue,maxValue,ra);//递归:如果取出来的数字和已取得的数字有重复就重新随机获取。

      }
    n++;
    }
    return tmp;
  }
 

感觉上用同一个随机种方便!!!

// 随机数个数
// 随机数下限
/// 随机数上限
public int[] GetRandomArray(int Number,int minNum,int maxNum)
{
int j;
int[] b=new int[Number];
Random r=new Random();
for(j=0;j<Number;j++)
{
int i=r.Next(minNum,maxNum+1);
int num=0;
for(int k=0;k<j;k++)
{
if(b[k]==i)
{
num=num+1;
}
}
if(num==0 )
{
b[j]=i;
}
else
{
j=j-1;
}
}
return b;
}

用云栖社区APP,舒服~

【云栖快讯】诚邀你用自己的技术能力来用心回答每一个问题,通过回答传承技术知识、经验、心得,问答专家期待你加入!  详情请点击

网友评论

awbeci
文章603篇 | 关注0
关注
是解决用户结构化数据搜索需求的托管服务,支持数据结构、搜索排序、数据处理自由定制。 为您的网... 查看详情
用于实时预测用户对物品偏好,支持企业定制推荐算法,支持A/B Test效果对比 查看详情
大数据开发套件(Data IDE),提供可视化开发界面、离线任务调度运维、快速数据集成、多人... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航