Current location - Quotes Website - Personality signature - How to design a random function with equal probability
How to design a random function with equal probability

Knuth Shuffle's shuffling algorithm has algorithm complexity O(n). The purpose of shuffling is to generate a string of random columns with equal probability.

1) How to ensure equal probability: select s elements from the r remaining elements, then the probability of selecting the next element is s/r.

2) Assume that the function bigrand() returns a large random integer (much larger than m and n), then bigrand()%n returns a random integer in the range [0,n-1]

p>

4) Application: For other applications, such as selecting the names of m cities from n cities, you can first sign the city names as 0,1,...,n-1

< p>Remember: the input of the random function we are facing is 0,1,...,n-1. For specific applications, the signature can be used to convert it into the corresponding 0,1,...,n-1

5) If you want to output in order, you can sort the operation objects first, and then sign [0,n-1]. In this way, by accessing the numbers in order, you can ensure that the output results are in order

< p>[java]

//Rearrange numbers in the range [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; //Generate a random number in the range [0, remaining-1]

swap(array[remaining], array[randValue]);

} //end for

return arr;

} // end knuthShuffle

Randomly select m numbers from n numbers, where [0,1,...,n-1] represents the signature of the number

[ java]

public void genknuth(int m,int n){

//Input control

if(m<=0 || n<=0 || m>n)

return ;

int select=m; //Select m elements

< p>int remaining=n; //n elements remaining

int randValue;

for(int i=0;i

randValue=bigrand()%(remaining-i);

if( randValue