Ho un array come questo:
var arr1 = ["a", "b", "c", "d"];
Come posso randomizzare / mischiare?
L'algoritmo di mischia imparziale de-facto è il Fisher-Yates (alias Knuth) Shuffle.
Vedi https://github.com/coolaj86/knuth-shuffle
Potete vedere una grande visualizzazione qui (e il post originale collegato a questo)
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);
Qualche altra informazione sull'algoritmo usato.
Ecco un'implementazione JavaScript del Durstenfeld shuffle, una versione ottimizzata al computer di 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;
}
}
L'algoritmo Fisher-Yates funziona scegliendo un elemento casuale per ogni elemento originale dell'array, e poi escludendolo dalla prossima estrazione. Proprio come scegliere a caso da un mazzo di carte.
Questa esclusione è fatta in un modo intelligente (inventato da Durstenfeld per essere usato dai computer) scambiando l'elemento scelto con l'elemento corrente, e poi scegliendo il prossimo elemento casuale dal resto. Per un'efficienza ottimale, il ciclo corre all'indietro in modo che la scelta casuale sia semplificata (può sempre iniziare da 0), e salta l'ultimo elemento perché non ci sono più altre scelte.
Il tempo di esecuzione di questo algoritmo è O(n). Notate che il rimescolamento viene fatto in-place. Quindi, se non volete modificare l'array originale, fatene prima una copia con .slice(0)
.
Il nuovo ES6 ci permette di assegnare due variabili contemporaneamente. Questo è particolarmente utile quando vogliamo scambiare i valori di due variabili, dato che possiamo farlo in una sola riga di codice. Ecco una forma più breve della stessa funzione, usando questa caratteristica.
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]];
}
}
Si potrebbe (o dovrebbe) usarlo come prototipo di Array:
Da 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;
}