如何设计随机函数

Knuth Shuffle的洗牌算法，算法复杂度O(n)，洗牌的目的是产生一串等概率的随机列。
1)如何保证等概率：从r个剩余的元素中选择s个元素，那么下一个元素选中的概率为s/r。
2)假设函数bigrand()返回一个大的随机整数（比m和n个大很多），那么bigrand()%n返回[0,n-1]范围的随机整数
4）应用：其他应用如从n个城市中选择出m个城市的名字，可以先对城市名进行签名标记为0,1,...,n-1
记住：我们面对的随机函数的输入是0,1,...,n-1，具体应用可以运用签名转换成成对应的0,1,...,n-1
5）如果要按序输出，可以先对操作对象排序，然后签名[0,n-1]，这样通过按序访问数，就能保证输出结果是有序的

//重新排列[0,n-1]范围内的数
public int[] knuthShuffle(int[] arr) {  
    if(arr==null)
	  return arr;
	  
    int randValue;  
    for (int remaining=arr.length; remaining>=0; remaining--) {  
        randValue = bigrand()%remaining; //产生[0,remaining-1]范围内的随机数
        swap(array[remaining], array[randValue]);  
    } //end for 
	
	return arr;
} //end knuthShuffle

从n个数中随机选择m个数,其中[0,1,...,n-1]代表数的签名

public void genknuth(int m,int n){
   //输入控制
   if(m<=0 || n<=0 || m>n)
     return ;

   int select=m;     //选择m个元素
   int remaining=n;  //剩余n个元素
   int randValue;
   for(int i=0;i<n;i++){
      randValue=bigrand()%(remaining-i); 
      if( randValue<select ){
	      System.out.println(i);
		  select--;
	  }//end if
   }//end for
}//end genknuth()

如何设计测试用例检查随机函数的正确性

PC机上是做不出真随机数的，只能做出伪随机数。真随机数需要硬件支持。洗牌洗得好不好，主要是看是不是够随机。概率问题，我们只有一个方法来做测试，那就是用统计的方式。
【测试方法】
测试洗牌程序也一样，需要通过概率的方式来做统计，是不是每张牌出现在每个位置的次数都是差不多的。
假设对[0,n-1]的n个数产生随机数，调用一次随机函数各个数字产生的概率是1/n，那么如果调用随机概率函数randNumber次，数i在每个位置上出现的次数应该为correctNumber=1/n*randNumber。假设实际数i在某个位置出现的次数是realNumber,则该位置处的误差error=1-realNumber/correctNumber。
举个例子，如测试样本1000次，列是每个位置出现的次数，行是各个数字的统计，出现概率应该是1/10，也就是理论上出现100次。调用随机函数100次，进行测试效果如下（测试结果来自该博客http://coolshell.cn/articles/8593.html）

0 1 2 3 4 5 6 7 8 9
--------------------------
0 | 74 108 123 102 93 198 40 37 52 173
1 | 261 170 114 70 49 28 37 76 116 79
2 | 112 164 168 117 71 37 62 96 116 57
3 | 93 91 119 221 103 66 91 98 78 40
4 | 62 60 82 90 290 112 95 98 71 40
5 | 46 60 63 76 81 318 56 42 70 188
6 | 72 57 68 77 83 39 400 105 55 44
7 | 99 79 70 73 87 34 124 317 78 39
8 | 127 112 102 90 81 24 57 83 248 76
9 | 54 99 91 84 62 144 38 48 116 264

然后统计误差即可。

【测试样本】
设置一个样本大小，做一下统计，然后计算一下误差值是否在可以容忍的范围内。比如：
样本：100万次
最大误差：10%以内
平均误差：5%以内（或者：90%以上的误差要小于5%）

随机函数有哪些应用

1、创新工场笔试题

第一个是让把一个数组打乱顺序，每个概率相等
2、给定一个函数rand()能产生0到n-1之间的等概率随机数，问如何产生0到m-1之间等概率的随机数？
思路：就是从n个数中随机生成m个数，上面已有代码，此处不做重复说明。
3、如何测试一个随机函数？

5、服务器每天会收到数以亿计的请求，但是目前服务器端不希望保存所有的请求，只想随机保存这些请求中的m个。试设计一种算法，能够使服务器实时保存m个请求，并使这些请求是从所有请求中的大致等概率被选中的结果。注意：不到一天的结束，是不能提前知道当天所有请求数n是多少的。

http://www.zhangliancheng.com/2012/09/random-selecting-numbers-from-unknown-length-interger-sequence/
5、给定一个函数rand5()，该函数可以随机生成1-5的整数，且生成概率一样。现要求使用该函数构造函数rand7()，使函数rand7()可以随机等概率的生成1-7的整数。
【思路】
我们可以利用rand5() + rand()%3来实现rand7()函数，这个方法确实可以产生1-7之间的随机数，但是是否生成的数字是等概率是？
rand()%3 产生0的概率是1/5，而产生1和2的概率都是2/5，所以这个方法产生6和7的概率大于产生5的概率。如何解决呢？
rand()产生[0,n-1]，把rand()视为n进制的一位数产生器，那么可以使用rand()*n+rand()来产生2位的n进制数，以此类推，可以产生3位，4位，5位...的n进制数。这种按构造n进制数的方式生成的随机数，必定能保证随机，而相反，借助其他方式来使用rand()产生随机数(如 rand5() + rand()%3 )都是不能保证概率平均的。
此题中n为5，因此可以使用rand5()*5+rand5()来产生2位的5进制数，范围就是1到25。再去掉22-25，剩余的除3，以此作为rand7()的产生器。

public int rand7() {  
    int x = 0; 
    while(x>21) 
    {  
        x = 5 * (rand5()-1) + rand5();  //rand5()生成[1,5]的整数，则rand5()-1生成[0,n-1]的整数
    }//end while 
    return x%7+1;  //x%7生成[0,7-1]的整数，则x%7+1生成[1,7]的整数
} //end rand7()

随机函数的几个技巧

rand()产生的是0~RAND_MAX之间的随机数。产生一定范围随机数的通用表示公式
要取得[a,b)的随机整数，使用(rand() % (b-a))+ a;
要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a;
要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1;
通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。
要取得a到b之间的随机整数，另一种表示：a + (int)b * rand() / (RAND_MAX + 1)。
要取得0～1之间的浮点数，可以使用rand() / double(RAND_MAX)。

怎么设计等概率的随机函数

如何设计随机函数

如何设计测试用例检查随机函数的正确性

随机函数有哪些应用

随机函数的几个技巧

相关推荐