如何设计等概率的随机函数

发布网友 发布时间：2022-04-20 09:08

我来回答

共1个回答

热心网友 时间：2023-09-26 15:37

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]，这样通过按序访问数，就能保证输出结果是有序的

[java]
<span style="font-size:18px">//重新排列[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</span>
从n个数中随机选择m个数,其中[0,1,...,n-1]代表数的签名

[java]
<span style="font-size:18px">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()</span>