日期:2014-05-20  浏览次数:20850 次

尽可能不重复的伪随机数生成器的高效实现

模仿 System.Random 提供的用户界面。可以从 System.Random 继承,也可以不。

1、尽可能不重复。含义是,Next 方法在没有达到必定会重复的时候,就不能重复。
比如,生成21-24之间(含21和24)的伪随机数,则生成前4个数不能重复,当然,第5个数不可避免会重复的。
NextDouble 方法也要求返回尽可能不重复的数,也就是说,在耗尽大于或等于 0.0 而小于 1.0 的双精度浮点数之前,不得重复。
NextBytes 方法则可以要求在数组长度小于或等于 byte.MaxValue+1 (也就是256)时,返回的数组元素不得重复。若数组长度大于256,则要求前256个元素不得重复。

2、随机性。我们知道,计算机不可能生成真正的随机序列,只能要求是伪随机序列。但我们可以要求这个序列不能有十分明显的规律,比如说,不能是等差数列、等比数列、斐波拿契数列,等等。

3、高效。要求实现尽量高效,这可能会和随机性发生矛盾。比如,是否要在内部保存已生成的序列,以判定是否重复。

以上抛砖引玉,还有很多方面都可以展开讨论。欢迎大家补充。



------解决方案--------------------
请教一个问题:随机数一定要“尽可能不重复”吗?
比如1到100之间的随机数,个人认为,如果是真正的随机数,那么前90个几乎一定会有重复。
或者说掷骰子,连扔6次正好不重复的出现1到6点,概率很低吧?
------解决方案--------------------
关注,最近有用到这个,希望能有个好点的算法..
------解决方案--------------------
在我的测试中生成100W,产生的重复值在200-500之间,耗时在20000MS-30000MS之间
生成的是字符串,如果生成数字的话,重复值会上升,耗时可能会更长
------解决方案--------------------
探讨
是啊,如果是真正的随机数,可以说,1到100之间的随机数,前90个几乎一定是会重复的。但是,我们这里讨论的是,尽可能不重复的伪随机数。这种伪随机数,可以保证1到100之间的随机数,…

------解决方案--------------------
学习...
------解决方案--------------------
C# code
namespace Skyiv
{
  using System.Collections.Generic;

  class Random : System.Random
  {
    private List<int> int32List = new List<int>();
    
    public override int Next(int minValue, int maxValue)
    {
      if (minValue == maxValue) return minValue;
      int next = base.Next(minValue, maxValue);
      if (int32List.Count >= maxValue - minValue) return next;
      if (int32List.Contains(next)) return Next(minValue, maxValue);
      int32List.Add(next);
      return next;
    }
  }
}

namespace Test
{
  using System;
  using Rand = Skyiv.Random;
  
  class Program
  {
    static void Main()
    {
      Rand r = new Rand();
      Console.WriteLine(r.Next(21,25));
      Console.WriteLine(r.Next(21,25));
      Console.WriteLine(r.Next(21,25));
      Console.WriteLine(r.Next(21,25));
      Console.WriteLine(r.Next(21,25));
    }
  }
}

------解决方案--------------------
学习,收藏
------解决方案--------------------
@_@~
------解决方案--------------------

1: 把你最终需要的结果(不重复的数)预先放在一个数组中, 因为rand函数产生的随机数会重复,我们不直接用,而是用来对应数组的下标
2: rand产生一个随机下标,我们就取出对应数组中的值(我们真正需要的随机数)
3: 然后用数组最后一个值来替换该下标数组中的值
4: 将产生随机下标的范围减少一
5: goto 2

注: 3中所谓数组最后一个值是指产生随机下标范围内的最后一个. 
如产生随机下标0-9, 第一次就用array[9]替换,第二次就用array[8]替换.

C/C++ code
#include<time.h>
#include<stdlib.h>
#include <stdio.h>

#define NUM 10

int main()
{
    int cont[NUM];
    int index, i;

    for (i=0; i<NUM; i++)
        cont[i] = i;

    srand((int)time(0));

    for (i=0; i<NUM; i++) {
        index = (int)((float)(NUM-i) * rand() / (RAND_MAX+1.0));
        printf("%d ", cont[index]);
        cont[index] = cont[NUM-1-i];
    }
    putchar('\n');

    return 0;
}

------解决方案--------------------
路过,学习
------解决方案--------------------
^ō^ 先占一楼...
------解决方案--------------------
不懂C#,平时用EXCEL解决1~100的正整数随机排序时,使用下面的方法:

搞一个2维数组
第一维为随机数,第二维为等差序列
对该数组按照第一维排序,就得到第二维的随机顺序排列。