Mám takéto pole:
var arr1 = ["a", "b", "c", "d"];
Ako ho môžem náhodne premiešať?
De facto nestranným algoritmom na náhodný výber je Fisher-Yatesov (alias Knuthov) náhodný výber.
Pozri https://github.com/coolaj86/knuth-shuffle.
Môžete si pozrieť skvelú vizualizáciu tu (a pôvodný príspevok odkaz na tento)
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);
Ďalšie informácie o použitom algoritme.
Tu je JavaScriptová implementácia Durstenfeld shuffle, počítačovo optimalizovanej verzie Fisher-Yatesovej metódy:
/**
* 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-Yatesov algoritmus funguje tak, že pre každý pôvodný prvok poľa vyberie jeden náhodný prvok a potom ho vylúči z ďalšieho žrebovania. Podobne ako pri náhodnom výbere z balíčka kariet.
Toto vylúčenie sa vykonáva šikovným spôsobom (ktorý vymyslel Durstenfeld pre použitie počítačmi) tak, že sa vybraný prvok zamení s aktuálnym prvkom a potom sa zo zvyšku vyberie ďalší náhodný prvok. Kvôli optimálnej efektívnosti sa cyklus spúšťa spätne, takže náhodný výber je zjednodušený (vždy môže začať od 0) a vynecháva posledný prvok, pretože už nie sú žiadne iné možnosti.
Čas behu tohto algoritmu je O(n). Všimnite si, že premiešavanie sa vykonáva na mieste. Ak teda nechcete upravovať pôvodné pole, vytvorte najprv jeho kópiu pomocou príkazu .slice(0)
.
Nové ES6 nám umožňuje priradiť dve premenné naraz. To sa hodí najmä vtedy, keď chceme vymeniť hodnoty dvoch premenných, pretože to môžeme urobiť v jednom riadku kódu. Tu je kratšia forma tej istej funkcie, ktorá využíva túto funkciu.
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]];
}
}
Mohli (alebo mali) by sme ho použiť ako prototyp z Array:
Od 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;
}