Jeg har et array som dette:
var arr1 = ["a", "b", "c", "d"];
Hvordan kan jeg randomisere / shuffle det?
Den de facto uforsigtige shuffle-algoritme er Fisher-Yates-shuffle (også kendt som Knuth-shuffle).
Se https://github.com/coolaj86/knuth-shuffle
Du kan se en fantastisk visualisering her (og det oprindelige indlæg linket til dette)
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);
Lidt mere info om den anvendte algoritme.
Her er en JavaScript-implementering af [Durstenfeld shuffle] (http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm), en computeroptimeret version af 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;
}
}
Fisher-Yates-algoritmen fungerer ved at vælge et tilfældigt element for hvert oprindeligt array-element og derefter udelukke det fra den næste trækning. Ligesom at vælge tilfældigt fra et sæt kort.
Denne udelukkelse sker på en smart måde (opfundet af Durstenfeld til brug for computere) ved at bytte det valgte element ud med det aktuelle element og derefter vælge det næste tilfældige element fra resten. For at opnå optimal effektivitet kører løkken baglæns, så det tilfældige valg er forenklet (det kan altid starte ved 0), og den springer det sidste element over, fordi der ikke længere er andre valgmuligheder.
Løbetiden for denne algoritme er O(n). Bemærk, at blandingen sker på stedet. Så hvis du ikke ønsker at ændre det oprindelige array, skal du først lave en kopi af det med .slice(0)
.
Det nye ES6 giver os mulighed for at tildele to variabler på én gang. Dette er især praktisk, når vi ønsker at bytte værdierne for to variabler, da vi kan gøre det i én kodelinje. Her er en kortere form af den samme funktion, der bruger denne funktion.
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]];
}
}
Man kunne (eller burde) bruge det som en prototype fra Array:
Fra 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;
}