function shuffle(array) {
var m = array.length, t, i;
// While there remain elements to shuffle…
while (m) {
// Pick a remaining element…
i = Math.floor(Math.random() * m--);
// And swap it with the current element.
t = array[m];
array[m] = array[i];
array[i] = t;
}
return array;
}
In Java
public class Program {
static void shuffle(int[] array) {
int n = array.length;
Random random = new Random();
// Loop over array.
for (int i = 0; i < array.length; i++) {
// Get a random index of the array past the current index.
// ... The argument is an exclusive bound.
// It will not go past the array's end.
int randomIndex = i + random.nextInt(n - i);
// Swap the random element with the present element.
int randomElement = array[randomIndex];
array[randomIndex] = array[i];
array[i] = randomElement;
}
}
public static void main(String[] args) {
int[] values = { 100, 200, 10, 20, 30, 1, 2, 3 };
// Shuffle integer array.
shuffle(values);
// Display elements in array.
for (int value : values) {
System.out.println(value);
}
}
}
Reservoir Sampling
Implementation: Select K Items from A Stream of N element
static void selectKItems(int stream[], int n, int k)
{
int i; // index for elements in stream[]
// reservoir[] is the output array. Initialize it with
// first k elements from stream[]
for (i = 0; i < k; i++) {
reservoir[i] = stream[i];
}
Random r = new Random();
// Iterate from the (k+1)th element to nth element
for (; i < n; i++)
{
// Pick a random index from 0 to i.
int j = r.nextInt(i + 1);
// If the randomly picked index is smaller than k,
// then replace the element present at the index
// with new element from stream
if(j < k) {
reservoir[j] = stream[i];
}
}
System.out.println("Following are k randomly selected items");
System.out.println(Arrays.toString(reservoir));
}
Weighted Random Distribution
Discusses different ways of performing weighted random selection and compare their pros and cons such as time and space complexity.
Different approaches
Expanding
One of the easiest solutions is to simply expand our array/list so that each entry in it appears as many times as its weight.
Pre-calculate accumulated sums of the weights for each element, and then use binary search to find where in the range that the random number belongs to, thus returning the corresponding element.