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-15) 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 remainingint randValue;
for(int i=0;i randValue=bigrand()%(remaining-i); if( randValue