Sélection de sous-ensembles random Du tableau

Qu'est-ce qu'un moyen propre de prendre un échantillon random sans remplacer un tableau dans javascript? Alors supposons qu'il y ait un tableau


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


et je veux prendre au hasard 5 valeurs uniques, c'est-à-dire pour générer un sous-ensemble random Longueur 5. Pour générer un échantillon random, Il serait possible de faire quelque chose comme:


x[Math.floor/Math.random//*x.length/];


Mais si cela est fait à plusieurs reprises, il risque de capturer le même record plusieurs fois.
Invité:

Emmanuel

Confirmation de:

je suggère
http://en.wikipedia.org/wiki/F ... uffle
Et prendre une pièce:


function getRandomSubarray/arr, size/ {
var shuffled = arr.slice/0/, i = arr.length, temp, index;
while /i--/ {
index = Math.floor//i + 1/ * Math.random///;
temp = shuffled[index];
shuffled[index] = shuffled[i];
shuffled[i] = temp;
}
return shuffled.slice/0, size/;
}

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


Veuillez noter que ce n'est pas la méthode la plus efficace d'obtention d'un petit sous-ensemble. random Un grand massif, puisqu'il donne sur l'ensemble de la matrice. Pour de meilleures performances, vous pouvez faire du shuffling partiel à la place:


function getRandomSubarray/arr, size/ {
var shuffled = arr.slice/0/, i = arr.length, min = i - size, temp, index;
while /i-- > min/ {
index = Math.floor//i + 1/ * Math.random///;
temp = shuffled[index];
shuffled[index] = shuffled[i];
shuffled[i] = temp;
}
return shuffled.slice/min/;
}

Fabien

Confirmation de:

Peu de retard pour une fête, mais cela pourrait être résolu avec l'aide d'une nouvelle méthode
http://underscorejs.org/#sample
underscore /underscore 1.5.2-Sept 2013/:


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

var randomFiveNumbers = _.sample/x, 5/;

Daniel

Confirmation de:

Ou ... Si vous utilisez underscore.js...


_und = require/'underscore'/;

...

function sample/a, n/ {
return _und.take/_und.shuffle/a/, n/;
}


Tout est assez simple.

Gregoire

Confirmation de:

À mon avis, tout le pont n'en vaut pas la peine. Vous avez juste besoin de vous assurer que votre échantillon est random, Et pas votre deck. Ce que vous pouvez faire est de choisir le montant
size

En face, puis changez chacun d'entre eux dans un tableau d'échantillonnage à une autre position. Ainsi, si vous autorisez le remplacement, vous obtenez de plus en plus de mélanges.


function getRandom/length/ { return Math.floor/Math.random//*/length//; }

function getRandomSample/array, size/ {
var length = array.length;

for/var i = size; i--;/ {
var index = getRandom/length/;
var temp = array[index];
array[index] = array[i];
array[i] = temp;
}

return array.slice/0, size/;
}


Cet algorithme consiste en tous
2*size

étapes si vous allumez la méthode
slice

, Choisir un échantillon random.

Suite Random

Faire un échantillon plus random, Nous pouvons choisir au hasard le point de départ de l'échantillon. Mais obtenir l'échantillon est un peu plus cher.


function getRandomSample/array, size/ {
var length = array.length, start = getRandom/length/;

for/var i = size; i--;/ {
var index = /start + i/%length, rindex = getRandom/length/;
var temp = array[rindex];
array[rindex] = array[index];
array[index] = temp;
}
var end = start + size, sample = array.slice/start, end/;
if/end > length/
sample = sample.concat/array.slice/0, end - length//;
return sample;
}


Qu'est-ce qui le rend plus random, Il s'agit donc du fait que lorsque vous venez de déplacer toujours les éléments avant, vous ne les obtenez généralement pas souvent dans l'échantillon, si le tableau d'échantillons est grand et que l'échantillon est petit. Ce ne serait pas un problème si une matrice n'avait pas eu à être toujours la même. Donc, qu'est-ce qui fait cette méthode, cela change cette position dans laquelle commence la zone de réévaluation.

Pas de remplacement

Pour ne pas copier un tableau d'échantillonnage et ne pas vous inquiéter de remplacement, vous pouvez faire ce qui suit, mais cela vous donnera
3*size

contre
2*size

.


function getRandomSample/array, size/ {
var length = array.length, swaps = [], i = size, temp;

while/i--/ {
var rindex = getRandom/length/;
temp = array[rindex];
array[rindex] = array[i];
array[i] = temp;
swaps.push/{ from: i, to: rindex }/;
}

var sample = array.slice/0, size/;

// Put everything back.
i = size;
while/i--/ {
var pop = swaps.pop//;
temp = array[pop.from];
array[pop.from] = array[pop.to];
array[pop.to] = temp;
}

return sample;
}


Pas de remplacement et plus Random

Appliquer l'algorithme qui a donné un peu plus random Échantillons à la fonction sans remplacement:


function getRandomSample/array, size/ {
var length = array.length, start = getRandom/length/,
swaps = [], i = size, temp;

while/i--/ {
var index = /start + i/%length, rindex = getRandom/length/;
temp = array[rindex];
array[rindex] = array[index];
array[index] = temp;
swaps.push/{ from: index, to: rindex }/;
}

var end = start + size, sample = array.slice/start, end/;
if/end > length/
sample = sample.concat/array.slice/0, end - length//;

// Put everything back.
i = size;
while/i--/ {
var pop = swaps.pop//;
temp = array[pop.from];
array[pop.from] = array[pop.to];
array[pop.to] = temp;
}

return sample;
}


Plus rapide...

Comme tous ces messages, Tastovka Fischer-Yate est utilisé ici. Mais j'ai supprimé un tableau en face de ma tête.


function getRandomSample/array, size/ {
var r, i = array.length, end = i - size, temp, swaps = getRandomSample.swaps;

while /i-- > end/ {
r = getRandom/i + 1/;
temp = array[r];
array[r] = array[i];
array[i] = temp;
swaps.push/i/;
swaps.push/r/;
}

var sample = array.slice/end/;

while/size--/ {
i = swaps.pop//;
r = swaps.pop//;
temp = array[i];
array[i] = array[r];
array[r] = temp;
}

return sample;
}
getRandomSample.swaps = [];

Hannah

Confirmation de:

Bien que je soutiens fermement l'utilisation de Yeits Fisher-Yeits Shuffling,

, Voici une très courte méthode d'atteindre un sous-ensemble random, mathématiquement correct, y compris le jeu vide et celui-ci beaucoup.

NOTE La solution dépend de
http://devdocs.io/lodash/index#sample
/
http://underscorejs.org/#sample
:

Lodash À 4 HEURES


const _ = require/'loadsh'/

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


Lodash En 3


const _ = require/'loadsh'/

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

Daniel

Confirmation de:

Vous pouvez supprimer des éléments du cuivre de la matrice comme ils le souhaitent. La performance n'est probablement pas idéale, mais cela peut être OK Pour ce dont vous avez besoin:


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

Gregoire

Confirmation de:

Si vous utilisez lodash, cette API Changé B. 4.x:


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


https://lodash.com/docs#sampleSize

Charles

Confirmation de:

Voici une autre mise en œuvre basée sur le shuffling de Fisher-Yate. Mais cela est optimisé pour le cas lorsque la taille de l'échantillon est nettement inférieure à la longueur de la matrice. Cette implémentation ne scanne pas l'ensemble de la matrice et n'alloit pas les matrices de la même taille que la matrice source. Il utilise des matrices raréfiques pour réduire la répartition de la 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;
}

Agathe

Confirmation de:

Afin que vous puissiez obtenir un échantillon de 5 Éléments:


var sample = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
.map/a => [a,Math.random//]/
.sort//a,b/ => {return a[1] < b[1] ? -1 : 1;}/
.slice/0,5/
.map/a => a[0]/;


Vous pouvez le définir comme une fonction à utiliser dans votre code:


var randomSample = function/arr,num/{ return arr.map/a => [a,Math.random//]/.sort//a,b/ => {return a[1] < b[1] ? -1 : 1;}/.slice/0,num/.map/a => a[0]/; }


Ou ajoutez-le à l'objet de la matrice elle-même:


Array.prototype.sample = function/num/{ return this.map/a => [a,Math.random//]/.sort//a,b/ => {return a[1] < b[1] ? -1 : 1;}/.slice/0,num/.map/a => a[0]/; };


Si vous voulez, vous pouvez diviser le code pour avoir 2 Les fonctions /Shuffle et Sample/:


Array.prototype.shuffle = function//{ return this.map/a => [a,Math.random//]/.sort//a,b/ => {return a[1] < b[1] ? -1 : 1;}/.map/a => a[0]/; };
Array.prototype.sample = function/num/{ return this.shuffle//.slice/0,num/; };

Fabien

Confirmation de:

Cela me manque-t-il peut-être quelque chose, mais il semble qu'il y ait une solution qui ne nécessite pas de complexité ou de dépassement des frais généraux potentiels:


[code]function sample/array,size/ {
const results = [],
sampled = {};
while/results.length<size !sampled[index]="" &&="" *="" ;="" <="" array.length="" array[index]="" code]="" const="" div="" if="" index="Math.trunc/Math.random//" results.length<array.length="" results.push="" results;="" return="" sampled[index]="true;" {="" }="" }[="">
</size>

Pour répondre aux questions, connectez-vous ou registre