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

模仿 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之间
生成的是字符串,如果生成数字的话,重复值会上升,耗时可能会更长
[解决办法]

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 10int 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维数组
第一维为随机数，第二维为等差序列
对该数组按照第一维排序，就得到第二维的随机顺序排列。 
 
[解决办法]
learn
[解决办法]
可以通过捕捉鼠标移动或键盘输入获得真正的随机数

[解决办法]
这里好好星星啊
学习了

[解决办法]
 

友情路过。
[解决办法]
好大只铁壳虫！！
[解决办法]
mark,学习
[解决办法]
除了研究意外我想知道是否还有其他意义。
[解决办法]
mark
[解决办法]
C# code
private void button2_Click(object sender, EventArgs e)        {            Dictionary<double, object> test = new Dictionary<double, object>();            int DoubleCount = 0;            for (int bi1 = 0; bi1 < 10000000; bi1++)            {                Guid temp = Guid.NewGuid();                double Return = BitConverter.ToDouble(temp.ToByteArray(), 0);                if (test.ContainsKey(Return))                {                    DoubleCount++;                }                else                {                    test.Add(Return,null);                }            }            this.Text = DoubleCount.ToString();        }
[解决办法]
C# code
Guid temp = Guid.NewGuid();double Return = BitConverter.ToDouble(temp.ToByteArray(), 0);
[解决办法]
C# code
Dictionary<double, object> test = new Dictionary<double, object>();            int DoubleCount = 0;            for (int a = 0; a < 10000000; a++)            {                               Guid temp = Guid.NewGuid();                ulong bi1 = BitConverter.ToUInt64(temp.ToByteArray(), 0);                bi1 = bi1 & 0x7FFFFFFFFFFFF;//00000000 00001111 11111111 11111111 11111111 11111111 11111111 1111111                bi1 = bi1 | 0x3FF8000000000000;                byte[] bb = BitConverter.GetBytes(bi1);                double Return = BitConverter.ToDouble(bb, 0);                if (test.ContainsKey(Return))                {                    DoubleCount++;                }                else                {                    test.Add(Return,null);                }
[解决办法]
 System.Security.Cryptography.RNGCryptoServiceProvider 的随机性会高很多

GUID的随机性好像是最高的，我的项目中经常使用GUID


[解决办法]
看了好多高手的写的东西，还真的是学到了不少东西。不过，我自己也学到了一些东西。我的老师曾经交了我一个算不重复的随机数的方法。和25楼的算法差不多。

我自己些了个算法：

class Program
   {
       static List<int> GetRandom(int maxCount)
       {
           Random rnd = new Random();
           List<int> lsOld = new List<int>();
           //为一个泛型集合添加1到maxCount的顺序数字
           for (int i = 0; i < maxCount; i++)
           {
               lsOld.Add(i);
           }

           int temp;
           int tempRnd;
           for (int i = maxCount; i > 0; i--)
           {
               tempRnd = rnd.Next(0, i - 1);
               temp = lsOld[i - 1];
               lsOld[i - 1] = lsOld[tempRnd];
               lsOld[tempRnd] = temp; 
 
           }
           return lsOld;
       }


       static void Main()
       {
           //只添加100个不重复的随即数
           List<int> lsAll;

           DateTime startTime = DateTime.Now;

           lsAll = GetRandom(1000000);


           //foreach (int i in lsAll)
           //{
           //    Console.WriteLine(i);
           //}

           TimeSpan timeSpan = DateTime.Now - startTime;

           Console.WriteLine("共消耗时间：" + timeSpan.TotalMilliseconds + "毫秒");
           Console.ReadKey();

       }
   }
[解决办法]
随机数就是要保证统计概率为1/N

如果按楼主设计
那么
1-N之间随机整数概率将在N/2次子后变大

例如N=5
第一次 3    概率1/5
第二次 1    概率1/4
第三次 4    概率1/3
第四次 2    概率1/2
第五次 5    概率1/1 必然

没有意义啊
[解决办法]
随机数产生的算法一般都是用正态分布或者指数分布或者博松分布来产生的吧
[解决办法]
在值域小数量级下可以做一个值域的全排列，然后随机抽取一个全排列作为一组随机数输出。


在大数量级下一般用循环链表来解决这个问题。

即将值域中所有值作为一个循环链表，从第一个节点开始，取一个随机数便向后推进随机个节点，输出这个节点并将其从循环链表中删除。

但是如果要在链表大小范围内抽取随机数，或许向后检索一个很大的个数的时候性能不够好，即使采用双向检索（将超过链表一半大小的检索转变为向后检索）也不能获得很好的性能，那么可以参考十字链表的做法，做一个循环十字链表。如下图结构：

 A1 -> A2 -> A3 -> A4 .....  A10 ->接A11
 ↓     ↓     ↓     ↓         ↓
->A11   A12   A13   A14....  A20
 ....


这里是按照十进制做的二维，如果我们要从A1向后14项，那么只需要按照向下的顺序向后推进1项，向前的顺序推进4项即可。
[解决办法]
刚查了一些统计计算方面的教材， 找到这个网站，希望能有帮助

http://www.fjtu.com.cn/fjnu/courseware/1017/course/_source/web/lesson/char6/j2.htm
[解决办法]
楼上曾经有人提到过用数组来记录是不是已经重复，当然这在数据量大的时候，效率是很难保证的。

我想，既然楼主那么执著的要实现一个不重复的随机，我倒是觉得可以把我们生成的记录保存到磁盘，然后参照B tree或者B+ tree的方式来形成索引，以提高遍历时的效率。
当然，因为中间有大量io操作，效率降低在所难免。

而取随机数，上文的朋友提到是一个正态分布或者泊松分布的问题，我也这么认为，那么，当你的取值区间很小时，你的重复的概率就高。 那么，我们可以通过增大取值区间来降低重复的概率。


说得不好，请大家不要见笑。
[解决办法]
说个整数情况下的想法：
1、MaxValue和MinValue只能通过new输入，创建好之后不能改变（否则就麻烦了）
2、Count=MaxValue-MinValue
3、随机产生n个数字（m1,m2,m3...mn），保证这些数字与Count互质
4、用每一个数字做等差数列，例如：
f1(x)=m1*x%Count;
f2(x)=f1(m2*x%Count);
...
fn(x)=fn-1(mn*x%Count);
5、每一次调用Next方法就是x++，然后对MinValue+fn(x)求解
6、当x=Count时，重新生成随机数m1,m2,m3...mn，x重置为0，达到重新排列的目的
附：可以通过增加m的数量，来减少规律