To achieve a random and predetermined shuffling of an array, the process can be divided into two main steps.
1. Generating pseudo-random numbers
While there are various options for PRNGs, the Xorshift algorithm stands out for its simplicity, speed in initialization and iteration, as well as uniform distribution.
This function requires an integer seed value and produces a random function that consistently generates floating-point values between 0 and 1.
const xor = seed => {
const baseSeeds = [123456789, 362436069, 521288629, 88675123]
let [x, y, z, w] = baseSeeds
const random = () => {
const t = x ^ (x << 11)
;[x, y, z] = [y, z, w]
w = w ^ (w >> 19) ^ (t ^ (t >> 8))
return w / 0x7fffffff
}
;[x, y, z, w] = baseSeeds.map(i => i + seed)
;[x, y, z, w] = [0, 0, 0, 0].map(() => Math.round(random() * 1e16))
return random
}
2. Shuffling using a customizable random function
The Fisher Yates shuffle is a highly efficient shuffling technique with a uniform distribution.
const shuffle = (array, random = Math.random) => {
let m = array.length
let t
let i
while (m) {
i = Math.floor(random() * m--)
t = array[m]
array[m] = array[i]
array[i] = t
}
return array
}
Bringing it all together
// Using the same seed for xor will yield the same shuffled output
console.log(shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9], xor(1))) // [ 3, 4, 2, 6, 7, 1, 8, 9, 5 ]
console.log(shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9], xor(1))) // [ 3, 4, 2, 6, 7, 1, 8, 9, 5 ]
// Changing the seed provided to the xor function results in a different output
console.log(shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9], xor(2))) // [ 4, 2, 6, 9, 7, 3, 8, 1, 5 ]