https://bigfrontend.dev/problem/can-you-shuffle-an-array
How would you implement a shuffle() ?
When passed with an array, it should modify the array inline to generate a randomly picked permutation at the same probability.
for an array like this:
const arr = [1, 2, 3, 4];there would be possibly 4! = 24 permutations
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]
your shuffle() should transform the array in one of the above array, at the same 1/24 probability.
notes
Your shuffle() will be called multiple times, to calculate the probability on each possible result, and test again standard deviation
ref: https://javascript.info/task/shuffle
/**
* @param {any[]} arr
*/
function shuffle(array) {
for (let i = array.length - 1; i > 0; i--) {
let j = Math.floor(Math.random() * (i + 1)); // random index from 0 to i
// swap elements array[i] and array[j]
// we use "destructuring assignment" syntax to achieve that
// same can be written as:
// let t = array[i]; array[i] = array[j]; array[j] = t
[array[i], array[j]] = [array[j], array[i]];
}
}Multiple runs of shuffle may lead to different orders of elements. For instance:
let arr = [1, 2, 3];
shuffle(arr);
// arr = [3, 2, 1]
shuffle(arr);
// arr = [2, 1, 3]
shuffle(arr);
// arr = [3, 1, 2]
<br />
shuffle(arr);
// ...function shuffle(array) {
array.sort(() => Math.random() - 0.5);
}
let arr = [1, 2, 3];
shuffle(arr);That somewhat works, because Math.random() - 0.5 is a random number that may be positive or negative, so the sorting function reorders elements randomly.
But because the sorting function is not meant to be used this way, not all permutations have the same probability.
For instance, consider the code below. It runs shuffle 1000000 times and counts appearances of all possible results:
function shuffle(array) {
array.sort(() => Math.random() - 0.5);
}
// counts of appearances for all possible permutations
let count = {
'123': 0,
'132': 0,
'213': 0,
'231': 0,
'321': 0,
'312': 0
};
for (let i = 0; i < 1000000; i++) {
let array = [1, 2, 3];
shuffle(array);
count[array.join('')]++;
}
// show counts of all possible permutations
for (let key in count) {
alert(`${key}: ${count[key]}`);
}An example result (depends on JS engine):
123: 250706
132: 124425
213: 249618
231: 124880
312: 125148
321: 125223
let's break this down:
-
Define the
shufflefunction: This function takes an array as an argument and sorts it using a comparator function that returns a random number between -0.5 and 0.5. This effectively shuffles the array, but it doesn't generate a truly random shuffle because not all permutations are equally likely. -
Initialize
countobject: This object will keep track of the number of times each possible permutation of the array [1, 2, 3] appears when the array is shuffled. -
Run the shuffle function multiple times: The code that follows (which is not shown in the excerpt) would run the
shufflefunction a large number of times (e.g., 1,000,000 times) and increment the count of the resulting permutation each time. -
Analyze the results: By looking at the counts of each permutation, you can see that some permutations appear more often than others. This demonstrates that the
shufflefunction does not generate a truly random shuffle, because in a truly random shuffle, all permutations would be equally likely.
The reason for this bias is that the Array.sort() method is not designed to be used with a comparator function that returns a random value. The sort order of two elements should be deterministic and based on the values of the elements themselves, not on a random number. When you use a random comparator function, the behavior of Array.sort() is not well-defined, and it can lead to biased results.
There are other good ways to do the task. For instance, there’s a great algorithm called Fisher-Yates shuffle. The idea is to walk the array in the reverse order and swap each element with a random one before it:
function shuffle(array) {
for (let i = array.length - 1; i > 0; i--) {
let j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
}
// counts of appearances for all possible permutations
let count = {
'123': 0,
'132': 0,
'213': 0,
'231': 0,
'321': 0,
'312': 0
};
for (let i = 0; i < 1000000; i++) {
let array = [1, 2, 3];
shuffle(array);
count[array.join('')]++;
}
// show counts of all possible permutations
for (let key in count) {
alert(`${key}: ${count[key]}`);
}The example output:
123: 166693
132: 166647
213: 166628
231: 167517
312: 166199
321: 166316
Looks good now: all permutations appear with the same probability.
Also, performance-wise the Fisher-Yates algorithm is much better, there’s no “sorting” overhead.
function generateRandomArray(n) {
const array = Array.from({ length: n }, (_, i) => i);
shuffle(array);
return array;
}
const array = generateRandomArray(10);
console.log(array); // [5, 7, 2, 4, 8, 6, 1, 9, 3, 0]
console.log(array); // [0, 5, 4, 9, 7, 8, 1, 2, 3, 6]
console.log(array); // [2, 1, 4, 0, 3, 5, 6, 7, 8, 9]- Randomizing Quiz Questions - Use Case Present questions in a random order.
function shuffle(array) { /*...*/ }
const questions = ['Q1', 'Q2', 'Q3', 'Q4'];
const shuffledQuestions = shuffle(questions);- Shuffling Playlist Songs - Use Case Play songs in a random order.
function shuffle(array) { /*...*/ }
const playlist = ['song1.mp3', 'song2.mp3', 'song3.mp3'];
const shuffledPlaylist = shuffle(playlist);- Randomizing Survey Responses - Use Case Minimize order bias in survey options.
function shuffle(array) { /*...*/ }
const responses = ['Strongly Agree', 'Agree', 'Neutral', 'Disagree', 'Strongly Disagree'];
const shuffledResponses = shuffle(responses);