Question Comment randomiser (mélanger) un tableau JavaScript?


J'ai un tableau comme celui-ci:

var arr1 = ["a", "b", "c", "d"];

Comment puis-je randomiser / mélanger?


872
2018-03-15 22:37


origine


Réponses:


L'algorithme de shuffle non biaisé de facto est le Shuffle de Fisher-Yates (aka Knuth).

Voir https://github.com/coolaj86/knuth-shuffle

Vous pouvez voir un grande visualisation ici (et le message original lié à cette)

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);

Quelques plus d'infos à propos de l'algorithme utilisé.


1084
2017-09-28 20:20



Voici une implémentation JavaScript du Mélange de Durstenfeld, une version optimisée par ordinateur de 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'algorithme de Fisher-Yates fonctionne en sélectionnant un élément aléatoire pour chaque élément de tableau original, puis en l'excluant du dessin suivant. Juste comme choisir au hasard à partir d'un jeu de cartes.

Cette exclusion est faite de manière intelligente (inventée par Durstenfeld pour une utilisation par les ordinateurs) en échangeant l'élément choisi avec l'élément courant, puis en choisissant l'élément aléatoire suivant dans le reste. Pour une efficacité optimale, la boucle tourne en arrière de sorte que la sélection aléatoire est simplifiée (elle peut toujours commencer à 0), et elle saute le dernier élément car il n'y a plus d'autres choix.

Le temps de fonctionnement de cet algorithme est O (n). Notez que le shuffle est fait sur place. Donc, si vous ne voulez pas modifier le tableau original, faites-en une copie d'abord avec .slice(0).

Mise à jour vers ES6 / ECMAScript 2015

Le nouvel ES6 nous permet d'assigner deux variables à la fois. Ceci est particulièrement pratique lorsque nous voulons échanger les valeurs de deux variables, comme nous pouvons le faire dans une ligne de code. Voici une forme plus courte de la même fonction, en utilisant cette fonctionnalité.

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]]; // eslint-disable-line no-param-reassign
    }
}

477
2017-09-06 04:55



[edit de la communauté: Cette réponse est incorrecte; voir les commentaires. Il est laissé ici pour référence future parce que l'idée n'est pas si rare.]

[1,2,3,4,5,6].sort(function() {
  return .5 - Math.random();
});

85
2018-04-13 13:59



On pourrait (ou devrait) l'utiliser comme protoype de Array:

De 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;
}

69
2018-03-31 05:29



Utilisez la bibliothèque underscore.js. La méthode _.shuffle() C'est sympa pour ce cas. Voici un exemple avec la méthode:

var _ = require("underscore");

var arr = [1,2,3,4,5,6];
// Testing _.shuffle
var testShuffle = function () {
  var indexOne = 0;
    var stObj = {
      '0': 0,
      '1': 1,
      '2': 2,
      '3': 3,
      '4': 4,
      '5': 5
    };
    for (var i = 0; i < 1000; i++) {
      arr = _.shuffle(arr);
      indexOne = _.indexOf(arr, 1);
      stObj[indexOne] ++;
    }
    console.log(stObj);
};
testShuffle();

56
2017-09-22 23:21



NOUVEAU!

Algorithme de shuffle Fisher-Yates plus court et probablement * plus rapide

  1. il utilise alors que ---
  2. au niveau du bit par rapport au sol (chiffres jusqu'à 10 chiffres décimaux (32 bits))
  3. supprimé fermetures inutiles et d'autres choses

function fy(a,b,c,d){//array,placeholder,placeholder,placeholder
 c=a.length;while(c)b=Math.random()*(--c+1)|0,d=a[c],a[c]=a[b],a[b]=d
}

taille du script (avec fy comme nom de fonction): 90bytes

DEMO http://jsfiddle.net/vvpoma8w/

* plus rapide probablement sur tous les navigateurs sauf le chrome.

Si vous avez des questions, vous avez juste à me les poser.

MODIFIER

oui c'est plus rapide

PERFORMANCE:  http://jsperf.com/fyshuffle

en utilisant les fonctions les mieux votées.

MODIFIER  Il y avait un calcul en excès (pas besoin de --c + 1) et personne n'a remarqué

plus court (4bytes) et plus rapide (test it!).

function fy(a,b,c,d){//array,placeholder,placeholder,placeholder
 c=a.length;while(c)b=Math.random()*c--|0,d=a[c],a[c]=a[b],a[b]=d
}

Mise en cache ailleurs var rnd=Math.random puis utilisez rnd() augmenterait également légèrement la performance sur les grands tableaux.

http://jsfiddle.net/vvpoma8w/2/

Version lisible (utiliser la version originale, c'est plus lent, les vars sont inutiles, comme les fermetures & ";", le code lui-même est aussi plus court ... peut-être lire ceci Comment "réduire" le code Javascript , parce que vous n'êtes pas en mesure de compresser le code suivant dans un minifiers javascript comme celui ci-dessus.)

function fisherYates( array ){
 var count = array.length,
     randomnumber,
     temp;
 while( count ){
  randomnumber = Math.random() * count-- | 0;
  temp = array[count];
  array[count] = array[randomnumber];
  array[randomnumber] = temp
 }
}

45
2018-04-05 15:38



Un moyen très simple pour les petits tableaux est simplement ceci:

const someArray = [1, 2, 3, 4, 5];

someArray.sort(() => Math.random() - 0.5);

Ce n'est probablement pas très efficace, mais pour les petites baies, cela fonctionne très bien. Voici un exemple pour que vous puissiez voir à quel point il est aléatoire (ou non) et s'il correspond ou non à votre cas.

const resultsEl = document.querySelector('#results');
const buttonEl = document.querySelector('#trigger');

const generateArrayAndRandomize = () => {
  const someArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
  someArray.sort(() => Math.random() - 0.5);
  return someArray;
};

const renderResultsToDom = (results, el) => {
  el.innerHTML = results.join(' ');
};

buttonEl.addEventListener('click', () => renderResultsToDom(generateArrayAndRandomize(), resultsEl));
<h1>Randomize!</h1>
<button id="trigger">Generate</button>
<p id="results">0 1 2 3 4 5 6 7 8 9</p>


23
2017-10-03 13:16



Vous pouvez le faire facilement avec la carte et le tri:

let unshuffled = ['hello', 'a', 't', 'q', 1, 2, 3, {cats: true}]

let shuffled = unshuffled
  .map((a) => ({sort: Math.random(), value: a}))
  .sort((a, b) => a.sort - b.sort)
  .map((a) => a.value)
  1. Nous mettons chaque élément dans le tableau dans un objet, et lui donnons une clé de tri aléatoire
  2. Nous trions en utilisant la clé aléatoire
  3. Nous démappage pour obtenir les objets originaux

Vous pouvez mélanger des tableaux polymorphes, et le tri est aussi aléatoire que Math.random, ce qui est assez bon pour la plupart des buts.

Puisque les éléments sont triés par rapport à des clés cohérentes qui ne sont pas régénérées à chaque itération, et que chaque comparaison provient de la même distribution, toute non-randomité dans la distribution de Math.random est annulée.


23
2018-04-01 21:23



Ajout à @Laurens Holsts réponse. Ceci est compressé à 50%.

function shuffleArray(d) {
  for (var c = d.length - 1; c > 0; c--) {
    var b = Math.floor(Math.random() * (c + 1));
    var a = d[c];
    d[c] = d[b];
    d[b] = a;
  }
  return d
};

19
2017-12-20 04:15



Avec ES2015 vous pouvez utiliser celui-ci:

Array.prototype.shuffle = function() {
  let m = this.length, i;
  while (m) {
    i = (Math.random() * m--) >>> 0;
    [this[m], this[i]] = [this[i], this[m]]
  }
  return this;
}

Usage:

[1, 2, 3, 4, 5, 6, 7].shuffle();

13
2017-08-09 15:37



var shuffle = function(array) {
   temp = [];
   for (var i = 0; i < array.length ; i++) {
     temp.push(array.splice(Math.floor(Math.random()*array.length),1));
   }
   return temp;
};

12
2018-06-25 15:25