Randomize ou Baralhe um Array em JavaScript

1. Baralhar um array dependendo do motor JavaScript
2. Medir a Aleatoriedade do Nosso Algoritmo Simples
3. Baralhar um array utilizando o algoritmo Fisher-Yates
4. Baralhar um Array com a biblioteca Underscore.js ou Lo-Dash

Neste tutorial, aprenderemos como baralhar ou randomizar um array em JavaScript; há muitas maneiras de baralhar um array em JavaScript - seja implementando algoritmos de baralhamento ou usando funções de baralhamento já existentes em algumas bibliotecas.

Baralhar um array é organizar o seu elemento aleatoriamente, por isso depende principalmente de como se reordena ou ordena o array com um grau de aleatoriedade.

Avancemos e descubramos diferentes formas de aleatorizar ou baralhar um array.

Baralhar um array dependendo do motor JavaScript

Comecemos por implementar um algoritmo simples de baralhamento do array, ordenando o array utilizando array.sort() mas utilizando alguma aleatoriedade gerada pela equação Math.random() - 0.5 e -0.5 assegura que cada vez que chamamos o algoritmo, o valor aleatório pode ser positivo ou negativo.

Vamos implementar esse algoritmo simples com o poder do motor JavaScript e imprimir o shuffled Array para consola utilizando Console.log():

function shuffleArray(inputArray) {
  inputArray.sort(() => Math.random() - 0.5);
}

var demoArray = [1, 3, 5];
shuffleArray(demoArray);
console.log(demoArray);

Resultado:

[1, 5, 3]

Medir a Aleatoriedade do Nosso Algoritmo Simples

A probabilidade das permutações dessa matriz pode ser calculada para verificar o quão excelente e aleatório o nosso algoritmo foi implementado.

Vamos ver como podemos medir a sua aleatoriedade.

1. Criar um dicionário que irá contar a aparência de todas as permutações.
2. Criar um laço que funcionará 1000000 vezes e cada vez aumentará a contagem da permutação formada
3. Imprimir as contagens de todas as permutações possíveis e observar as probabilidades entre elas.

Este algoritmo de medição simples pode ser implementado como o seguinte:

function shuffleArray(inputArray) {
  inputArray.sort(() => Math.random() - 0.5);
}

// counts of the appearances for all possible permutations
var countDic = {
  '153': 0,
  '135': 0,
  '315': 0,
  '351': 0,
  '531': 0,
  '513': 0,
};

// Creating the loop
for (var i = 0; i < 1000000; i++) {
  var arr = [1, 5, 3];
  shuffleArray(arr);
  countDic[arr.join('')]++;
}

// Print the counts of all possible permutations
for (var key in countDic) {
  console.log(`${key}: ${countDic[key]}`);
}

Resultado:

135: 62256
153: 375832
315: 62976
351: 311865
513: 124518
531: 62553

A partir da saída acima, podemos ver claramente o viés como 135, 315, e 531 aparecem muito menos do que outros e contagens tão semelhantes umas às outras.

Baralhar um array utilizando o algoritmo Fisher-Yates

Este algoritmo simples baseado no motor JavaScript não é fiável na secção passada, mas um grande algoritmo chamado Fisher-Yates é melhor no que diz respeito à sua eficiência e fiabilidade.

A ideia por detrás do algoritmo Fisher-Yates é caminhar para a matriz em ordem inversa e trocar cada elemento com um aleatório antes dele. O Fisher-Yates é um algoritmo simples mas muito eficiente e rápido.

Vamos implementar o algoritmo Fisher-Yates:

function fisherYatesShuffle(arr) {
  for (var i = arr.length - 1; i > 0; i--) {
    var j = Math.floor(Math.random() * (i + 1));  // random index
    [arr[i], arr[j]] = [arr[j], arr[i]];          // swap
  }
}

var tmpArray = [1, 3, 5];
fisherYatesShuffle(tmpArray);
console.log(tmpArray);

Vamos então explicá-lo passo a passo:

1. for(var i =array.length-1 ; i>0 ;i--) a para loop que andará sobre o array numa ordem inversa.
2. Math.floor( Math.random() * (i + 1) ) Gerar um índice aleatório que varia entre 0 e i.
3. [arr[i],arr[j]]=[arr[j],arr[i]] está a trocar os elementos arr[i] e arr[j] entre si utilizando a sintaxe Destructuring Assignment.

Resultado:

(3) [3, 1, 5]

Agora vamos testar Fisher-Yates o mesmo que fizemos antes:

// counts of the appearances for all possible permutations
var countDic = {
  '153': 0,
  '135': 0,
  '315': 0,
  '351': 0,
  '531': 0,
  '513': 0,
};

// Creating the loop
for (var i = 0; i < 1000000; i++) {
  var arr = [1, 5, 3];
  fisherYatesShuffle(arr);
  countDic[arr.join('')]++;
}

// Print the counts of all possible permutations
for (var key in countDic) {
  console.log(`${key}: ${countDic[key]}`);
}

Resultado:

135: 166734
153: 166578
315: 166908
351: 166832
513: 166535
531: 166413

A partir da saída acima, podemos ver a grande diferença entre o algoritmo Fisher-Yates e o algoritmo simples que implementámos antes e o quão fiável é o algoritmo Fisher-Yates.

Baralhar um Array com a biblioteca Underscore.js ou Lo-Dash

A famosa biblioteca Underscore.js também fornece uma função de baralhamento que pode aleatorizar directamente um array sem a necessidade de escrever a sua implementação de qualquer algoritmo.

Vejamos o seguinte exemplo de utilização do método _.shuffle().

Primeiro, precisamos de importar a biblioteca utilizando o Cloudflare CDN dentro do HTML Template,

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.15/lodash.min.js"></script>

Depois utilizamos o método _.shuffle() como:

var tmpUnderscoreArray = [1, 3, 5];
resultArray = _.shuffle(tmpUnderscoreArray);
console.log(resultArray);

Resultado:

(3) [1, 5, 3]