Ik heb een matrix als deze:
var arr1 = ["a", "b", "c", "d"];
Hoe kan ik die randomiseren / shuffelen?
Het de-facto onbevooroordeelde shuffle algoritme is de Fisher-Yates (aka Knuth) Shuffle.
Zie https://github.com/coolaj86/knuth-shuffle
Je kunt een geweldige visualisatie hier zien (en de oorspronkelijke post gelinkt aan deze)
function shuffle(array) {
var currentIndex = array.length, temporaryValue, randomIndex;
// While there remain elements to shuffle...
while (0 !== currentIndex) {
// Pick a remaining element...
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;
// And swap it with the current element.
temporaryValue = array[currentIndex];
array[currentIndex] = array[randomIndex];
array[randomIndex] = temporaryValue;
}
return array;
}
// Used like so
var arr = [2, 11, 37, 42];
arr = shuffle(arr);
console.log(arr);
Wat meer info over het gebruikte algoritme.
Hier is een JavaScript implementatie van de Durstenfeld shuffle, een computer-geoptimaliseerde versie van Fisher-Yates:
/**
* Randomize array element order in-place.
* Using Durstenfeld shuffle algorithm.
*/
function shuffleArray(array) {
for (var i = array.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * (i + 1));
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
Het Fisher-Yates algoritme kiest een willekeurig element voor elk oorspronkelijk array-element, en sluit het dan uit bij de volgende trekking. Net als het willekeurig kiezen uit een spel kaarten.
Dit uitsluiten gebeurt op een slimme manier (uitgevonden door Durstenfeld voor gebruik door computers) door het gekozen element te verwisselen met het huidige element, en dan het volgende willekeurige element te kiezen uit de rest. Voor een optimale efficiëntie loopt de lus achteruit, zodat de willekeurige keuze vereenvoudigd wordt (hij kan altijd bij 0 beginnen), en slaat hij het laatste element over omdat er geen andere keuzes meer zijn.
De looptijd van dit algoritme is O(n). Merk op dat de shuffle in-place wordt gedaan. Dus als je de originele array niet wilt wijzigen, maak er dan eerst een kopie van met .slice(0)
.
De nieuwe ES6 staat ons toe om twee variabelen tegelijk toe te wijzen. Dit is vooral handig als we de waarden van twee variabelen willen verwisselen, omdat we dat in één regel code kunnen doen. Hier is een kortere vorm van dezelfde functie, gebruikmakend van deze functie.
function shuffleArray(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
}
Men zou het kunnen (of moeten) gebruiken als een protoype van Array:
Van ChristopheD:
Array.prototype.shuffle = function() {
var i = this.length, j, temp;
if ( i == 0 ) return this;
while ( --i ) {
j = Math.floor( Math.random() * ( i + 1 ) );
temp = this[i];
this[i] = this[j];
this[j] = temp;
}
return this;
}