Comment rendre aléatoire (shuffle) un tableau JavaScript?

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

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

OriginalL'auteur deadrunk

Utiliser le underscore.js de la bibliothèque. La méthode _.shuffle() est bien pour cette affaire.
Voici un exemple de 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();

OriginalL'auteur vn_grv

Vous pouvez le faire facilement avec une carte et de 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 mettre chaque élément du tableau dans un objet, et lui donner un aléatoire de la clé de tri
2. Nous de tri à l'aide de la clé aléatoire
3. Nous détacher pour obtenir les objets d'origine

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

Puisque les éléments sont triés contre cohérente clés qui ne sont pas régénérés à chaque itération, et chaque comparaison tire de la même distribution, tous les non-aléatoire dans la distribution de Mathématiques.aléatoire est annulée.

OriginalL'auteur superluminary

Certaines des réponses pourrait être raccourci à l'aide de ES6 syntaxe.

ES6 Pur, Itératif

const getShuffledArr = arr => {
    const newArr = arr.slice()
    for (let i = newArr.length - 1; i > 0; i--) {
        const rand = Math.floor(Math.random() * (i + 1));
        [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
    }
    return newArr
};

Personnellement, j'utilise cette fonction car il est pur, relativement simple, et selon mes tests sur Google Chrome le plus efficace (par rapport à d'autres pure versions).

Shuffle réseau En place

function getShuffledArr (array){
    for (let i = array.length - 1; i > 0; i--) {
        const rand = Math.floor(Math.random() * (i + 1));
        [array[i], array[rand]] = [array[rand], array[i]]
    }
}

---

De fiabilité et de Performance

Comme vous pouvez le voir dans cette page, il y a eu des solutions incorrectes offert ici dans le passé. Donc, avec la fiabilité et la performance à l'esprit, j'ai écrit cette fonction permet de tester toute pure (sans effets secondaires) tableau de randomisation des fonctions. Je l'ai utilisé pour tester toutes les options présentées dans cette réponse.

function testShuffledArrayFun(getShuffledArrayFun){
    const arr = [0,1,2,3,4,5,6,7,8,9]

    let countArr = arr.map(el=>{
        return arr.map(
            el=> 0
        )
    }) //  For each possible position in the shuffledArr and for 
       //  each possible value, we'll create a counter. 
    const t0 = performance.now()
    const n = 1000000
    for (let i=0 ; i<n ; i++){
        //  We'll call getShuffledArrayFun n times. 
        //  And for each iteration, we'll increment the counter. 
        const shuffledArr = getShuffledArrayFun(arr)
        shuffledArr.forEach(
            (value,key)=>{countArr[key][value]++}
        )
    }
    const t1 = performance.now()
    console.log(`Count Values in position`)
    console.table(countArr)

    const frequencyArr = countArr.map( positionArr => (
        positionArr.map(  
            count => count/n
        )
    )) 

    console.log("Frequency of value in position")
    console.table(frequencyArr)
    console.log(`total time: ${t1-t0}`)
}

---

Tapuscrit de type pour un pur tableau de randomisation fonction

Vous pouvez utiliser l'une des opérations suivantes.

type GetShuffledArr= <T>(arr:Array<T>) => Array<T> 
interface IGetShuffledArr{
    <T>(arr:Array<T>): Array<T>
}

---

Autres Options

ES6 Pur, Récursive

const getShuffledArr = arr => {
    if (arr.length === 1) {return arr};
    const rand = Math.floor(Math.random() * arr.length);
    return [arr[rand], ...getShuffledArr(arr.filter((_, i) => i != rand))];
};

Cette version est moins efficace que l'itératif version pure.

ES6 Pur à l'aide du tableau.carte

function getShuffledArr (arr){
    return [...arr].map( (_, i, arrCopy) => {
        var rand = i + ( Math.floor( Math.random() * (arrCopy.length - i) ) );
        [arrCopy[rand], arrCopy[i]] = [arrCopy[i], arrCopy[rand]]
        return arrCopy[i]
    })
}

Cette version est légèrement moins efficace que l'itératif version pure.

ES6 Pur à l'aide du tableau.réduire

function getShuffledArr (arr){
    return arr.reduce( 
        (newArr, _, i) => {
            var rand = i + ( Math.floor( Math.random() * (newArr.length - i) ) );
            [newArr[rand], newArr[i]] = [newArr[i], newArr[rand]]
            return newArr
        }, [...arr]
    )
}

Cette version est légèrement moins efficace que l'itératif version pure.

OriginalL'auteur Ben Carp

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

OriginalL'auteur Tophe

Une solution récursive:

function shuffle(a,b){
    return a.length==0?b:function(c){
        return shuffle(a,(b||[]).concat(c));
    }(a.splice(Math.floor(Math.random()*a.length),1));
};

OriginalL'auteur Julian

Tout d'abord, jetez un oeil ici pour un grand visuel comparaison de différentes méthodes de tri en javascript.

Deuxièmement, si vous avez un coup d'oeil sur le lien ci-dessus, vous constaterez que le random order trier semble fonctionner relativement bien par rapport aux autres méthodes, tout en étant très facile et rapide à mettre en œuvre, comme illustré ci-dessous:

function shuffle(array) {
  var random = array.map(Math.random);
  array.sort(function(a, b) {
    return random[array.indexOf(a)] - random[array.indexOf(b)];
  });
}

Modifier: comme l'a souligné @gregers, la fonction de comparaison est appelé avec les valeurs plutôt que des indices, qui est pourquoi vous devez utiliser des indexOf. Notez que cette modification rend le code moins adapté pour les grands tableaux comme indexOf s'exécute en O(n) fois.

OriginalL'auteur 0sh

encore une autre mise en œuvre de Fisher-Yates, en utilisant le mode strict:

function shuffleArray(a) {
    "use strict";
    var i, t, j;
    for (i = a.length - 1; i > 0; i -= 1) {
        t = a[i];
        j = Math.floor(Math.random() * (i + 1));
        a[i] = a[j];
        a[j] = t;
    }
    return a;
}

OriginalL'auteur Raphael C

Moderne, court inline solution à l'aide de ES6 caractéristiques:

['a','b','c','d'].map(x => [Math.random(), x]).sort(([a], [b]) => a - b).map(([_, x]) => x);

(à des fins pédagogiques)

OriginalL'auteur icl7126

Si il y a un certain nombre d'implémentations déjà conseillé, mais je sens que nous pouvons faire plus court et plus facile à l'aide d'une boucle forEach, donc on n'a pas besoin de s'inquiéter sur le calcul de la longueur du tableau et aussi nous pouvons éviter d'utiliser une variable temporaire.

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

myArr.forEach((val, key) => {
  randomIndex = Math.ceil(Math.random()*(key + 1));
  myArr[key] = myArr[randomIndex];
  myArr[randomIndex] = val;
});
//see the values
console.log('Shuffled Array: ', myArr)

OriginalL'auteur Hafizur Rahman

À partir d'un point de vue théorique, la façon la plus élégante de le faire, à mon humble avis, est d'obtenir une unique nombre aléatoire entre 0 et n!-1 et pour calculer une association de {0, 1, …, n!-1} de toutes les permutations de (0, 1, 2, …, n-1). Tant que vous pouvez utiliser une (pseudo-)aléatoire générateur suffisamment fiable pour obtenir un tel numéro, sans aucun biais important, vous avez suffisamment d'informations pour la réalisation de ce que vous voulez sans avoir besoin de plusieurs autres nombres aléatoires.

Lors du calcul avec IEEE754 double précision nombres flottants, vous pouvez vous attendre de votre générateur aléatoire pour fournir environ 15 décimales. Puisque vous avez 15!=1,307,674,368,000 (à 13 chiffres), vous pouvez utiliser les fonctions suivantes avec des tableaux contenant jusqu'à 15 éléments et supposons qu'il n'y aura pas de biais significatif avec des tableaux renfermant jusqu'à 14 éléments. Si vous travaillez sur une taille fixe de problème qui nécessite de calculer plusieurs fois cette lecture aléatoire de l'opération, vous pouvez essayer le code suivant qui peut être plus rapide que les autres codes car il utilise Math.random qu'une seule fois (il s'agit de plusieurs opérations de copie).

La fonction suivante ne sera pas utilisé, mais je donne quand même; il renvoie l'index d'une permutation de (0, 1, 2, …, n-1) selon l'une à une cartographie utilisées dans ce message (le plus naturel lors de l'énumération permuations); il est prévu pour fonctionner avec jusqu'à 16 éléments:

function permIndex(p) {
    var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000];
    var tail = [];
    var i;
    if (p.length == 0) return 0;
    for(i=1;i<(p.length);i++) {
        if (p[i] > p[0]) tail.push(p[i]-1);
        else tail.push(p[i]);
    }
    return p[0] * fact[p.length-1] + permIndex(tail);
}

La réciproque de la fonction précédente (nécessaire pour votre propre question) est au-dessous; il est prévu pour fonctionner avec jusqu'à 16 éléments; elle renvoie la permutation de l'ordre n de (0, 1, 2, …, s-1):

function permNth(n, s) {
    var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000];
    var i, j;
    var p = [];
    var q = [];
    for(i=0;i<s;i++) p.push(i);
    for(i=s-1; i>=0; i--) {
        j = Math.floor(n / fact[i]);
        n -= j*fact[i];
        q.push(p[j]);
        for(;j<i;j++) p[j]=p[j+1];
    }
    return q;
}

Maintenant, ce que vous voulez, simplement:

function shuffle(p) {
    var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000];
    return permNth(Math.floor(Math.random()*fact[p.length]), p.length).map(
            function(i) { return p[i]; });
}

Il devrait travailler jusqu'à 16 éléments avec un peu théorique de biais (si imperceptible à partir d'un point de vue pratique); il peut être considéré comme pleinement utilisable pour 15 éléments; avec des tableaux contenant moins de 14 éléments, vous pouvez en toute sécurité envisager il n'y aura absolument pas de parti pris.

OriginalL'auteur Thomas Baruchel

Aléatoire tableau à l'aide du tableau.splice()

function shuffleArray(array) {
   var temp = [];
   var len=array.length;
   while(len){
      temp.push(array.splice(Math.floor(Math.random()*array.length),1)[0]);
      len--;
   }
   return temp;
}
//console.log("Here >>> "+shuffleArray([4,2,3,5,8,1,0]));

démo

OriginalL'auteur Saravanan Rajaraman