算法同上题
package Hard; import CtCILibrary.AssortedMethods; /**
* Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen. 译文： 写一个函数，随机地从大小为n的数组中选取m个整数。要求每个元素被选中的概率相等。
*
*/
public class S18_3 { /* Random number between lower and higher, inclusive */
public static int rand(int lower, int higher) {
return lower + (int)(Math.random() * (higher - lower + 1));
} public static void swap(int[] a, int n, int m){
int tmp = a[n];
a[n] = a[m];
a[m] = tmp;
} /* pick M elements from original array, using only elements 0 through i (inclusive).*/
public static int[] pickMRecursively(int[] original, int m, int i) {
if (i + 1 < m) { // Not enough elements
return null;
} else if (i + 1 == m) { // Base case -- copy first m elements into array
int[] set = new int[m];
for (int k = 0; k < m; k++) {
set[k] = original[k];
}
return set;
} else {
int[] set = pickMRecursively(original, m, i - 1);
int k = rand(0, i);
if (k < m) {
set[k] = original[i];
}
return set;
}
} /* pick M elements from original array. Clone original array so that
* we don’t destroy the input. */
public static int[] pickMRandomly(int[] original, int m) {
for (int i = 0; i < m; i++) {
int k = rand(i, original.length-1); // 产生i到n-1间的随机数
swap(original, i, k);
}
int[] subset = new int[m];
for(int i=0; i<m; i++){
subset[i] = original[i];
}
return subset;
} public static void main(String[] args) {
int[] cards = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
System.out.println(AssortedMethods.arrayToString(cards));
int[] set = pickMRandomly(cards, 4);
System.out.println(AssortedMethods.arrayToString(set));
}
}