Random

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: https://bost.ocks.org/mike/shuffle/

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: https://www.dotnetperls.com/shuffle-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

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"); 
    System.out.println(Arrays.toString(reservoir));
}

Weighted Random Distribution

https://www.electricmonk.nl/log/2009/12/23/weighted-random-distribution/

https://www.electricmonk.nl/docs/weighted_random_distribution/weighted_random_distribution.pdf

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.

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

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.

Conclusion

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