写一个函数,随机地从大小为n的数组中选取m个整数。要求每个元素被选中的概率相等。

原创
2016/11/28 11:27
阅读数 834

随机地从大小替n的数组中选取m个整数

www.MyException.Cn  网友分享于:2013-10-08  浏览:30次

随机地从大小为n的数组中选取m个整数

问题:写一个函数,随机地从大小为n的数组中选取m个整数。要求每个元素被选中的概率相等。

 

分析:这道题目和随机洗牌算法类似,只需要随机选取1个元素, 然后在剩下的元素里面随机选取下一个元素,不断这样操作即可。

这样做能保证每个元素选中的概率一样吗?也就是选中每个元素的概率都是1/n? 答案是YES,让我们来做一下简单的计算。

  • 选第1个元素:在n个中随机选,因此概率为1/n

  • 选第2个元素:在剩下的n-1个中随机选:1/(n-1),由于第1次没有选中它, 而是在另外n-1个中选:(n-1)/n,因此概率为:(n-1)/n * 1/(n-1) = 1/n

  • 选第3个元素:同上:(n-1)/n * (n-2)/(n-1) * 1/(n-2) = 1/n

    。。。。。

因此,按照这种方法选取k个元素,每个元素都是以1/n的概率被选出来的

 

基本思想:

                首先在下标0---n之间随机生成一个下标,将这个下标对应的数和数组的第一个数交换位置;然后从小标1----n之间随机生成一个数,将下标对应的

数和数组的第二个数交换位置。依次这样下去,知道找出m个数。

[java] view plain copy

 

  1. public class RandomM {  
  2.   
  3.     public static void main(String[] args) {  
  4.         // TODO Auto-generated method stub  
  5.         int[] arr=new int[10];  
  6.         for(int i=0;i<10;i++){  
  7.             arr[i]=i;  
  8.         }  
  9.         for(int n: selectM(arr, 5)){  
  10.             System.out.println(n);  
  11.         }  
  12.     }  
  13.       
  14.     //从长度为n的数组中随机的选择m个整数  
  15.     public static int[] selectM(int[] arr,int m){  
  16.         int len=arr.length;  
  17.         if(m>arr.length)  
  18.             throw new RuntimeException("xxxxx");  
  19.         int[] res=new int[m];  
  20.         for(int i=0;i<m;i++){  
  21.             int randomIndex=len-1-new Random().nextInt(len-i);  
  22.             res[i]=arr[randomIndex];  
  23.             int tmp=arr[randomIndex];  
  24.             arr[randomIndex]=arr[i];  
  25.             arr[i]=tmp;  
  26.         }  
  27.         return res;  
  28.     }  
  29.   
  30. }
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部