Campionamento di un sottoinsieme casuale da un array

Qual è un modo pulito di prendere un campione casuale, senza la sostituzione da un array in javascript? Quindi supponiamo che ci sia un array

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

e voglio campionare casualmente 5 valori unici; cioè generare un sottoinsieme casuale di lunghezza 5. Per generare un campione casuale si potrebbe fare qualcosa del tipo:

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

Ma se questo viene fatto più volte, c’è il rischio di afferrare la stessa voce più volte.

Suggerisco di mischiare una copia dell’array usando il rimescolamento di Fisher-Yates e prendendo una fetta:

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

Si noti che questo non sarà il metodo più efficiente per ottenere un piccolo sottoinsieme casuale di un array di grandi dimensioni in quanto rimuove l’intera matrice inutilmente. Per prestazioni migliori potresti invece fare un rimescolamento parziale:

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

Un po ‘tardi per la festa, ma questo potrebbe essere risolto con il nuovo metodo di campionamento del underscore (sottolineatura 1.5.2 – Settembre 2013):

 var x = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]; var randomFiveNumbers = _.sample(x, 5); 

O … se usi underscore.js …

 _und = require('underscore'); ... function sample(a, n) { return _und.take(_und.shuffle(a), n); } 

Abbastanza semplice

È ansible rimuovere gli elementi da una copia dell’array mentre li si seleziona. Le prestazioni probabilmente non sono l’ideale, ma potrebbe essere OK per ciò di cui hai bisogno:

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

Mentre sostengo fortemente l’uso di Fisher-Yates Shuffle, come suggerito da Tim Down , ecco un metodo molto breve per ottenere un sottoinsieme casuale come richiesto, matematicamente corretto, incluso il set vuoto e il set stesso.

La soluzione di nota dipende da lodash / underscore :

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

Secondo me, non penso che sia necessario mischiare l’intero mazzo. Devi solo assicurarti che il tuo campione non sia casuale nel tuo mazzo. Quello che puoi fare è selezionare l’ammontare della size dalla parte anteriore, quindi scambiare ciascuno nell’array di campionamento con un’altra posizione al suo interno. Quindi, se permetti la sostituzione, diventi sempre più mischiato.

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

Questo algoritmo è solo passi di 2*size , se si include il metodo slice , per selezionare il campione casuale.


Più casuale

Per rendere il campione più casuale, possiamo selezionare casualmente il punto di partenza del campione. Ma è un po ‘più costoso ottenere il campione.

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

Ciò che rende questo più casuale è il fatto che quando si mischia sempre gli elementi anteriori si tende a non trovarli molto spesso nel campione se l’array di campionamento è grande e il campione è piccolo. Questo non sarebbe un problema se l’array non dovesse essere sempre lo stesso. Quindi, ciò che questo metodo fa è cambiare questa posizione in cui inizia la regione mescasting.


Nessuna sostituzione

Per non dover copiare l’array di campionamento e non preoccuparti della sostituzione, puoi fare quanto segue ma ti dà 3*size rispetto alla 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; } 

Nessuna sostituzione e più casuale

Per applicare l’algoritmo che ha dato un po ‘più di campioni casuali alla funzione di non sostituzione:

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

Più veloce…

Come tutti questi post, questo usa il Fisher-Yates Shuffle. Ma, ho rimosso l’overhead di copiare l’array.

 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 = []; 

Se stai usando l’API lodash modificata in 4.x:

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

https://lodash.com/docs#sampleSize

Ecco un’altra implementazione basata su Fisher-Yater Shuffle. Ma questo è ottimizzato per il caso in cui la dimensione del campione è significativamente inferiore alla lunghezza dell’array. Questa implementazione non esegue la scansione dell’intero array né assegna matrici grandi quanto l’array originale. Usa array sparsi per ridurre l’allocazione della memoria.

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