Our first instinct on this problem might be to randomly pick elements from the array and put them into our new subset array. But then, what if we pick the same element twice? Ideally, we’d want to somehow “shrink” the array to no longer contain that element. Shrinking is expensive though because of all the shifting required.
Instead of shrinking / shifting, we can swap the element with an element at the beginning of the array and then “remember” that the array now only includes elements j and greater. That is, when we pick subset[0] to be array[k], we replace array[k] with the first element in the array. When we pick subset[1], we consider array[0] to be “dead” and we pick a random element y between 1 and array.size(). We then set subset[1] equal to array[y], and set array[y] equal to array[1]. Elements 0 and 1 are now “dead.” Subset[2] is now chosen from array[2] through array[array.size()], and so on.
/* Random number between lower and higher, inclusive */
public static int rand(int lower, int higher) {
return lower + (int)(Math.random() * (higher - lower + 1));
}
/* 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) {
int[] subset = new int[m];
int[] array = original.clone();
for (int j = 0; j < m; j++) {
int index = rand(j, array.length - 1);
subset[j] = array[index];
array[index] = array[j]; // array[j] is now “dead”
}
return subset;
}
Posts
No comments:
Post a Comment