Comment randomiser ou mélanger un tableau en JavaScript

1. Mélanger un tableau en fonction du moteur JavaScript
2. Mesurer le caractère aléatoire de notre algorithme simple
3. Mélanger un tableau en utilisant l’algorithme de mélange de Fisher-Yates
4. Mélanger un tableau avec la bibliothèque Underscore.js ou Lo-Dash

Dans ce tutoriel, nous apprendrons à mélanger ou à rendre aléatoire un tableau en JavaScript. Il existe de nombreuses façons de mélanger un tableau en JavaScript, que ce soit en implémentant des algorithmes de mélange ou en utilisant des fonctions de mélange déjà existantes dans certaines bibliothèques.

Mélanger un tableau consiste à disposer ses éléments de manière aléatoire, ce qui dépend donc principalement de la manière dont vous réorganisez ou triez le tableau avec un certain degré d’aléa.

Allons de l’avant et découvrons différentes façons de randomiser ou de mélanger un tableau.

Mélanger un tableau en fonction du moteur JavaScript

Commençons par mettre en œuvre un algorithme simple de brassage de tableaux en triant le tableau à l’aide de array.sort() mais en utilisant un certain caractère aléatoire généré par l’équation Math.random() - 0.5 et -0.5, ce qui garantit que chaque fois que nous appelons l’algorithme, la valeur aléatoire peut être positive ou négative.

Implémentons cet algorithme simple avec la puissance du moteur JavaScript et imprimons le tableau mélangé sur la console en utilisant console.log() :

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

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

Production :

[1, 5, 3]

Mesurer le caractère aléatoire de notre algorithme simple

La probabilité des permutations de ce réseau peut être calculée pour vérifier l’excellence et le caractère aléatoire de notre algorithme.

Voyons comment nous pouvons mesurer son caractère aléatoire.

1. Créer un dictionnaire qui comptera l’apparition pour toutes les permutations.
2. Créez une boucle qui s’exécutera 1000000 fois et qui augmentera à chaque fois le nombre de permutations formées
3. Imprimez les comptes de toutes les permutations possibles et observez les probabilités entre elles.

Cet algorithme de mesure simple peut être implémenté comme suit :

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]}`);
}

Production :

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

A partir de la sortie ci-dessus, nous pouvons voir clairement le biais car 135, 315 et 531 apparaissent beaucoup moins que d’autres et donc des comptes similaires les uns aux autres.

Mélanger un tableau en utilisant l’algorithme de mélange de Fisher-Yates

Cet algorithme simple basé sur le moteur JavaScript n’est pas fiable dans la section précédente, mais un grand algorithme appelé Fisher-Yates est meilleur en ce qui concerne son efficacité et sa fiabilité.

L’idée derrière l’algorithme de Fisher-Yates est de marcher vers le tableau dans l’ordre inverse et d’échanger chaque élément avec un élément aléatoire avant lui. Fisher-Yates est un algorithme simple mais très efficace et rapide.

Implémentons l’algorithme de 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);

Alors expliquons-le pas à pas :

1. for(var i =array.length-1 ; i>0 ;i--) a pour boucle qui va marcher sur le tableau dans un ordre inverse.
2. Math.floor(Math.random() * (i + 1)) Génération d’un indice aléatoire qui se situe entre 0 et i.
3. [arr[i],arr[j]]=[arr[j],arr[i]] est l’échange des éléments arr[i] et arr[j] entre eux en utilisant la syntaxe des affectations de déstructuration.

Production :

(3) [3, 1, 5]

Maintenant, testons Fisher-Yates comme nous l’avons fait auparavant :

// 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]}`);
}

Production :

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

De la sortie ci-dessus, vous pouvez voir la grande différence entre l’algorithme de Fisher-Yates et l’algorithme simple que nous avons implémenté auparavant et la fiabilité de l’algorithme de Fisher-Yates.

Mélanger un tableau avec la bibliothèque Underscore.js ou Lo-Dash

La célèbre bibliothèque Underscore.js fournit également une fonction de shuffle qui peut directement rendre aléatoire un tableau sans qu’il soit nécessaire d’écrire votre implémentation d’un quelconque algorithme.

Voyons l’exemple suivant d’utilisation de la méthode _.shuffle().

Tout d’abord, nous devons importer la bibliothèque en utilisant Cloudflare CDN dans le modèle HTML,

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

Ensuite, nous utilisons la méthode _.shuffle() comme :

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

Production:

(3) [1, 5, 3]