Comment on page


About math random, not "random question".

Shuffle a Deck of Cards - Fisher–Yates Shuffle

A de facto algorithm to shuffle an array: Fisher–Yates Shuffle
A great visualization for the algorithm:
In JavaScript
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
Modified based on Sam Allen's implementation:
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.
// Display elements in array.
for (int value : values) {

Reservoir Sampling

See also: 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");

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


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.
weights = {
'A': 2,
'B': 4,
'C': 3,
'D': 1
['A', 'A', 'B', 'B', 'B', 'B', 'C', 'C', 'C', 'D']

In-place (Unsorted)

In-place (sorted)


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.
weights = {
'A': 2,
'B': 4,
'C': 3,
'D': 1
[(2, 'A'), (5, 'C'), (9, 'B'), (10, 'D')]
See Random Pick with Weight from LeetCode.


If you need
speedy selections
  • Use expanded if the number of items in your set is low, and your weights are not very high.
  • Use pre-calculated if your set has lots of numbers and/or your weights are high.
If you need
speedy updates
  • Use in-place (unsorted) for the fastest updates.
  • Use in-place (sorted) for somewhat slower updates and somewhat faster selections.
If you need
low memory usage
  • Don’t use expanded.
If you need
  • Use expanded or in-place (unsorted).