Shuffle/Randomize an array in JavaScript using Knuth Fisher-Yates shuffle algorithm
Knuth (Fisher-Yates) shuffle algorithm is an algorithm for randomly shuffling the elements of an array. The Knuth Fisher-Yates shuffle is used to randomly permute given input (list). The permutations generated by this algorithm occur with the same probability. The complexity of this algorithm is O(n). Check the solutions below.
The Fisher-Yates algorithm works by picking one random element for each original array element, and then excluding it from the next draw. Just like randomly picking from a deck of cards.
This exclusion is done in a clever way (invented by Durstenfeld for use by computers) by swapping the picked element with the current element, and then picking the next random element from the remainder. For optimal efficiency, the loop runs backwards so that the random pick is simplified (it can always start at 0), and it skips the last element because there are no other choices anymore.
JavaScript
// Shuffle an array in JavaScript function shuffle(array) { var m = array.length, temp, i; // Check if there's still elements remaining while (m) { // Pick remaining element i = Math.floor(Math.random() * m--); // Swap it with the current element temp = array[m]; array[m] = array[i]; array[i] = temp; } return array; }
Java
// Shuffle an array in Java public static void knuth(int[] array) { Random r = new Random(); for (int i = array.length - 1; i > 0; i--) { int index = r.nextInt(i); // swap int tmp = array[index]; array[index] = array[i]; array[i] = tmp; } }
Python
// Shuffle an array in Python from random import randrange def shuffle(x): for i in range(len(x)-1, 0, -1): j = randrange(i + 1) x[i], x[j] = x[j], x[i] x = list(range(10)) shuffle(x) print("shuffled array -- ", x)