Eu tenho um conjunto como este:
var arr1 = ["a", "b", "c", "d"];
Como posso aleatorizar / baralhar?
O algoritmo de embaralhamento imparcial de fato é o Fisher-Yates (também conhecido como Knuth) Shuffle.
Ver https://github.com/coolaj86/knuth-shuffle
Você pode ver uma grande visualização aqui (e o post original ligado a isto)
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);
Mais algumas informações sobre o algoritmo utilizado.
Aqui está uma implementação JavaScript do Durstenfeld shuffle, uma versão otimizada para computador do 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;
}
}
O algoritmo Fisher-Yates funciona escolhendo um elemento aleatório para cada elemento da matriz original, e depois excluindo-o do próximo sorteio. Tal como a escolha aleatória de um baralho de cartas.
Esta exclusão é feita de uma forma inteligente (inventada por Durstenfeld para uso por computadores), trocando o elemento escolhido com o elemento atual e, em seguida, escolhendo o próximo elemento aleatório do restante. Para uma eficiência ótima, o loop roda para trás para que o pick aleatório seja simplificado (pode sempre começar em 0), e ele pula o último elemento porque não há mais nenhuma outra escolha.
O tempo de execução deste algoritmo é O(n). Note que o embaralhamento é feito no local. Então se você não quiser modificar o array original, faça uma cópia dele primeiro com .slice(0)
.
O novo ES6 permite-nos atribuir duas variáveis ao mesmo tempo. Isto é especialmente útil quando queremos trocar os valores de duas variáveis, pois podemos fazê-lo em uma linha de código. Aqui está uma forma mais curta da mesma função, usando este recurso.
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]];
}
}
Pode-se (ou deve-se) usá-lo como um protótipo do Array:
Do 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;
}