Skip to content

Instantly share code, notes, and snippets.

@czep
Created May 7, 2021 18:33
Show Gist options
  • Save czep/560e4cb181342eec7281210ad2aeac44 to your computer and use it in GitHub Desktop.
Save czep/560e4cb181342eec7281210ad2aeac44 to your computer and use it in GitHub Desktop.
Iterative Fisher-Yates permutation in Javascript
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>Fisher-Yates</title>
</head>
<body>
<h1>Fisher-Yates Shuffling in Javascript</h1>
<p>Open the console, ensure that the accompanying javascript file is also available, then click the button below.</p>
<button type="button" id="runtests">Run tests</button>
<script type="text/javascript" src="fisher-yates.js"></script>
</body>
</html>
//
// fisher-yates.js
// See: https://czep.net/21/obfuscate.html
// This test pre-computes all possible "shuffles" of 8 elements
// comparing the results of in-place Fisher-Yates to an iterative method.
// NOTE: using 1-based arrays in some places to simplify notation
// the 0th index of the array is just a dummy placeholder
class FisherYatesTester {
constructor(n) {
this.n = n;
this.seq = Array.from({length: n+1}, (_, i) => i);
this.runs = 0;
this.matches = 0;
this.results = new Map;
this.shuffles = [];
}
init() {
// pre-generate all possible shuffles
let template = Array.from({length: this.n}, (_, i) => i + 1);
let a = Array.from(template);
do {
this.shuffles.push(Array.from(a));
// successively +1 until we max out the permutations
let i;
for (i = this.n - 1; i >= 0; i--) {
if (a[i] >= this.n) {
a[i] = template[i];
}
else {
a[i]++;
break;
}
}
if (i < 0)
break;
} while (1);
}
// in-place Fisher-Yates shuffle
shuffle1(shuf) {
let res = Array.from(this.seq);
for (let i = 1; i < this.n ; i++) {
const r = shuf[i-1];
const tmp = res[i];
res[i] = res[r];
res[r] = tmp;
}
return res.toString();
}
// iterative Fisher-Yates shuffle
shuffle2(shuf) {
let i;
let ptr = new Map();
let res = [0];
for (i = 1; i < this.n ; i++) {
const r = shuf[i-1];
// determine which value to move to the output sequence
if (ptr.has(r)) {
res.push(ptr.get(r));
}
else {
res.push(r);
}
// update the map of pointers to swapped values
if (ptr.has(i)) {
ptr.set(r, ptr.get(i));
ptr.delete(i);
}
else {
if (r > i) {
ptr.set(r, i);
}
}
}
// finalize for i == n
if (ptr.has(i)) {
res.push(ptr.get(i));
ptr.delete(i);
}
else {
res.push(i);
}
if (ptr.size > 0) {
console.log(`Failed to empty the map: ${ptr.size}`);
}
return res.toString();
}
loop() {
for (const shuf of this.shuffles) {
let res1 = this.shuffle1(shuf);
let res2 = this.shuffle2(shuf);
this.runs++;
this.matches += res1 === res2;
if (res1 !== res2) {
console.log(`Results DO NOT MATCH for "${shuf.toString()}": 1 = "${res1}" 2 = "${res2}"`);
}
if (this.results.has(res1)) {
console.log(`Permutation ALREADY EXISTS in map: ${res1}`);
this.results.set(res1, 1 + this.results.get(res1));
}
else {
this.results.set(res1, 1);
}
}
console.log(`In ${this.runs} runs, there were ${this.matches} matches.`);
console.log(`Number of shuffles: ${this.shuffles.length}`);
console.log(`Number of observed permutations: ${this.results.size}`);
}
}
function main() {
// The argument to the tester specifies the size of the input range
// This will generate n! permutations so keep this number smallish.
s = new FisherYatesTester(8);
s.init();
s.loop();
}
document.addEventListener("DOMContentLoaded", function() {
console.log("Ready to go.");
const btnrun = document.getElementById('runtests');
btnrun.addEventListener('click', function (e) {
e.preventDefault();
main();
}, false);
}, false);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment