Échantillonner un sous-ensemble aléatoire à partir d'un tableau

Question

Quelle est une manière propre de prendre un échantillon aléatoire, sans remplacement, à partir d'un tableau en javascript? Supposons donc qu'il y a un tableau

x = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

et je veux échantillonner de manière aléatoire 5 valeurs uniques; c'est-à-dire générer un sous-ensemble aléatoire de longueur 5. Pour générer un échantillon aléatoire, on pourrait faire quelque chose comme:

x[Math.floor(Math.random()*x.length)];

Mais si cela est fait plusieurs fois, il y a un risque de saisir la même entrée plusieurs fois.

Answer 1

Vous pouvez supprimer les éléments d'une copie du tableau au fur et à mesure que vous les sélectionnez. Les performances ne sont probablement pas optimales, mais cela pourrait convenir à vos besoins :

function getRandom(arr, size) {
  var copy = arr.slice(0), rand = [];
  for (var i = 0; i < size && i < copy.length; i++) {
    var index = Math.floor(Math.random() * copy.length);
    rand.push(copy.splice(index, 1)[0]);
  }
  return rand;
}

Answer 2

Pour les très grandes tableaux, il est plus efficace de travailler avec des index plutôt qu'avec les éléments du tableau.

C'est ce que j'ai fini par avoir après n'avoir rien trouvé que j'aimais sur cette page.

/**
 * Obtenir un sous-ensemble aléatoire d'un tableau
 * @param {Array} arr - Tableau dont on veut prendre un échantillon.
 * @param {Number} sample_size - Taille de l'échantillon à extraire.
 * @param {Boolean} return_indexes - Si true, retourne les indexes plutôt que les éléments
 * @returns {Array|Boolean} - Un tableau contenant un sous-ensemble aléatoire des éléments ou des indexes.
 */
function getArraySample(arr, sample_size, return_indexes = false) {
    if(sample_size > arr.length) return false;
    const sample_idxs = [];
    const randomIndex = () => Math.floor(Math.random() * arr.length);
    while(sample_size > sample_idxs.length){
        let idx = randomIndex();
        while(sample_idxs.includes(idx)) idx = randomIndex();
        sample_idxs.push(idx);
    }
    sample_idxs.sort((a, b) => a > b ? 1 : -1);
    if(return_indexes) return sample_idxs;
    return sample_idxs.map(i => arr[i]);
}

Answer 3

Mon approche sur cela est de créer une méthode getRandomIndexes que vous pouvez utiliser pour créer un tableau des indexes que vous allez extraire du tableau principal. Dans ce cas, j'ai ajouté une logique simple pour éviter le même index dans l'échantillon. voici comment ça fonctionne

const getRandomIndexes = (longueur, taille) => {
  const indexes = [];
  const créés = {};

  while (indexes.length < taille) {
    const aléatoire = Math.floor(Math.random() * longueur);
    if (!créés[aléatoire]) {
      indexes.push(aléatoire);
      créés[aléatoire] = true;
    }
  }
  return indexes;
};

Cette fonction, indépendamment de ce que vous avez, va vous donner un tableau d'indexes que vous pouvez utiliser pour extraire les valeurs de votre tableau de longueur longueur, donc pourrait être échantillonné par

const monTableau = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']

getRandomIndexes(monTableau.length, 3).map(i => monTableau[i])

Chaque fois que vous appelez la méthode, vous obtiendrez un échantillon différent de monTableau. à ce stade, cette solution est cool mais pourrait être encore meilleure pour échantillonner des tailles différentes. si vous voulez le faire, vous pouvez utiliser

getRandomIndexes(monTableau.length, Math.ceil(Math.random() * 6)).map(i => monTableau[i])

vous donnera une taille d'échantillon différente de 1 à 6 à chaque fois que vous l'appellerez.

J'espère que cela vous a aidé :D

Answer 4

Underscore.js fait environ 70ko. Si vous n'avez pas besoin de tous les extras, rando.js ne fait que 2ko (97% plus petit), et fonctionne de cette manière :

console.log(randoSequence([8, 6, 7, 5, 3, 0, 9]).slice(-5));

Vous pouvez voir qu'il garde les indices originaux par défaut au cas où deux valeurs seraient les mêmes mais que vous vous souciez toujours de laquelle a été choisie. Si vous n'en avez pas besoin, vous pouvez simplement ajouter une map, comme ceci :

console.log(randoSequence([8, 6, 7, 5, 3, 0, 9]).slice(-5).map((i) => i.value));

Answer 5

D3-array utilise l'algorithme de mélange Fisher-Yeates pour réorganiser aléatoirement les tableaux. C'est une fonction de mutation - ce qui signifie que le tableau original est réorganisé sur place, ce qui est bon pour les performances.

D3 est pour le navigateur - c'est plus compliqué à utiliser avec node.

https://github.com/d3/d3-array#shuffle

npm install d3-array

    //import {shuffle} from "d3-array" 

    let x = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];

    d3.shuffle(x)

    console.log(x) // il est mélangé

Si vous ne voulez pas muter le tableau original

    let x = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];

    let shuffled_x = d3.shuffle(x.slice()) //appeler slice sans paramètres renvoie une copie du tableau original

    console.log(x) // non mélangé
    console.log(shuffled_x)