Array Shuffling

[ajhsu]

Shuffle Algorithm

• A good shuffling algorithm is unbiased.

Shuffle Algorithm Comparison

https://bost.ocks.org/mike/shuffle/compare.html

Fisher–Yates shuffle

The Fisher–Yates shuffle is an algorithm for generating a random permutation of a finite sequence—in plain terms, the algorithm shuffles the sequence.

1. The algorithm effectively puts all the elements into a hat; it continually determines the next element by randomly drawing an element from the hat until no elements remain.

2. The algorithm produces an unbiased permutation: every permutation is equally likely.

3. The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place.

Fisher–Yates shuffle on Wikipedia

• https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
• https://stackoverflow.com/questions/6274339/how-can-i-shuffle-an-array
• https://stackoverflow.com/questions/2450954/how-to-randomize-shuffle-a-javascript-array
• https://bost.ocks.org/mike/shuffle/
• https://gaohaoyang.github.io/2016/10/16/shuffle-algorithm/
• https://www.youtube.com/watch?v=CoI4S7z1E1Y

JavaScript Implementation

/**
 * Fisher-Yates Modern Shuffle Algorithm
 */

let arr = [1, 2, 3, 4, 5, 6, 7, 8];

function swapArrayElement(arr, a, b) {
  if (a > arr.length || b > arr.length) return;
  let tmp = arr[a];
  arr[a] = arr[b];
  arr[b] = tmp;
}

/**
 * Mutable Shuffling
 * Time complexity: (n - 1) + 2 => O(n)
 */
function mutableShuffle(arr) {
  for (let iter = arr.length - 1; iter > 0; iter--) {
    let r = Math.floor(Math.random() * (iter + 1));
    swapArrayElement(arr, iter, r);
  }
}

/**
 * Immutable Shuffling
 */
function immutableShuffle(arr) {
  let nextArr = arr.slice();
  mutableShuffle(nextArr);
  return nextArr;
}

/**
 * Shuffle the array without messing it
 */
console.log("Immutable Shuffling");
console.log("New Array:", immutableShuffle(arr));
console.log("Original Array:", arr);

/**
 * Shuffle the original array in place
 */
console.log("Mutable Shuffling");
mutableShuffle(arr);
console.log("Shuffled Array:", arr);

/**
 * Shuffle via Array.shuffle();
 */
Array.prototype.shuffle = function() {
  mutableShuffle(this);
  return this;
};
console.log("Shuffling via Array.shuffle()");
console.log("Shuffled Array:", arr.shuffle());