É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

Alors que je soutiens vivement l'utilisation du mélange Fisher-Yates, comme suggéré par Tim Down, voici une méthode très courte pour obtenir un sous-ensemble aléatoire tel que demandé, mathématiquement correct, incluant l'ensemble vide et l'ensemble donné lui-même.

Note que la solution dépend de lodash / underscore:

Lodash v4

const _ = require('loadsh')

function subset(arr) {
    return _.sampleSize(arr, _.random(arr.length))
}

Lodash v3

const _ = require('loadsh')

function subset(arr) {
    return _.sample(arr, _.random(arr.length));
}

Answer 2

Beaucoup de ces réponses parlent de clonage, de mélange, de découpage du tableau d'origine. Je me demandais pourquoi cela aide d'un point de vue entropie/distribution.

Je ne suis pas expert mais j'ai écrit une fonction d'exemple en utilisant les indexes pour éviter toute mutation de tableau — cela ajoute cependant à un Set. Je ne sais pas non plus comment est la distribution aléatoire sur cela mais le code était assez simple pour, je pense, mériter une réponse ici.

function sample(array, size = 1) {
  const { floor, random } = Math;
  let sampleSet = new Set();
  for (let i = 0; i < size; i++) {
    let index;
    do { index = floor(random() * array.length); }
    while (sampleSet.has(index));
    sampleSet.add(index);
  }
  return [...sampleSet].map(i => array[i]);
}

const words = [
  'confus', 'étonnant', 'menthe', 'moteur', 'équipe', 'lâche', 'coopératif',
  'réparation', 'non écrit', 'détaillé', 'chanceux', 'valeur', 'chiens', 'air', 'trouvé',
  'tordu', 'inutile', 'traitement', 'surprise', 'colline', 'doigt', 'animal de compagnie',
  'ajustement', 'prétendu', 'revenu'
];

console.log(sample(words, 4));

Answer 3

Si vous utilisez lodash, l'API a changé en 4.x :

const oneItem = _.sample(arr);
const nItems = _.sampleSize(arr, n);

https://lodash.com/docs#sampleSize

Answer 4

Peut-être que je manque quelque chose, mais il semble qu'il y a une solution qui ne nécessite pas la complexité ou le potentiel de surcharge d'un mélange :

function sample(array,size) {
  const results = [],
    sampled = {};
  while(results.length

Answer 5

Voici une autre implémentation basée sur Fisher-Yates Shuffle. Mais celle-ci est optimisée pour le cas où la taille de l'échantillon est significativement plus petite que la taille du tableau. Cette implémentation ne parcourt pas l'ensemble du tableau ni n'alloue de tableaux aussi grands que le tableau d'origine. Elle utilise des tableaux clairsemés pour réduire l'allocation de mémoire.

function getRandomSample(array, count) {
    var indices = [];
    var result = new Array(count);
    for (let i = 0; i < count; i++ ) {
        let j = Math.floor(Math.random() * (array.length - i) + i);
        result[i] = array[indices[j] === undefined ? j : indices[j]];
        indices[j] = indices[i] === undefined ? i : indices[i];
    }
    return result;
}