The first thing that comes to mind - to choose a random element from an array and put them in a new array. But what if we choose the same item twice? Ideally, we need to reduce the array so as to throw out the selected item. But the reduction of the array rather time-consuming operation, since it requires the displacement elements.
Rather than cut (move) array, you can put an element (to change elements of seats) in the beginning of the array, and "remember" that now begins with an array element j. If the item subset [0] becomes an element of array [k], then we have to replace the element array [k] the first element in the array. When we turn to the element subset [1], we mean that the element array [0] is "dead", and select a random element from the range from 1 to array.size (). Now subset [1] = array [y] and array [y] = subset [1]. Elements 0 and 1 "dead" and the subset [2] is selected in the range of array [2] to array [array.size ()], etc.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public static int rand(int lower, int higher) {
return lower + (int)(Math.random() * (higher - lower + 1));
}
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];
}
return subset;
}
|
0 коммент.:
Post a Comment