Comment on page

# Random

About math random, not "random question".

**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**

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);

}

}

}

**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));

}

Discusses different ways of performing weighted random selection and compare their pros and cons such as time and space complexity.

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']

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')]

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

**simplicity**

- Use expanded or in-place (unsorted).

Last modified 3yr ago