javascript - repetir - Muestreo de un subconjunto aleatorio de una matriz

random javascript entre dos numeros

Question

¿Cuál es una forma limpia de tomar una muestra aleatoria, sin reemplazo de una matriz en javascript? Entonces, supongamos que hay una matriz

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

y quiero muestrear aleatoriamente 5 valores únicos; es decir, generar un subconjunto aleatorio de longitud 5. Para generar una muestra aleatoria uno podría hacer algo como:

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

Pero si esto se hace muchas veces, existe el riesgo de que se agarre la misma entrada varias veces.

Answer 1

Puede eliminar los elementos de una copia de la matriz a medida que los seleccione. El rendimiento probablemente no sea el ideal, pero podría estar bien para lo que necesita:

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

O ... si usas underscore.js ...

_und = require(''underscore'');

...

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

Suficientemente simple.

Answer 3

Un poco tarde para la fiesta, pero esto podría resolverse con el nuevo método de muestra de subrayado (guión bajo 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);

Answer 4

Sugiero barajar una copia de la matriz con la mezcla de Fisher-Yates y tomar una porción:

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

Tenga en cuenta que este no será el método más eficiente para obtener un pequeño subconjunto aleatorio de una matriz grande porque mezcla toda la matriz innecesariamente. Para un mejor rendimiento, podrías hacer una mezcla parcial:

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

Answer 5

Aquí hay otra implementación basada en Fisher-Yater Shuffle. Pero este está optimizado para el caso en que el tamaño de muestra es significativamente menor que la longitud de la matriz. Esta implementación no analiza toda la matriz ni asigna matrices tan grandes como la matriz original. Utiliza matrices dispersas para reducir la asignación de 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;
}

Answer 6

En mi opinión, no creo que deba barajar todo el mazo. Solo debes asegurarte de que tu muestra sea aleatoria, no tu mazo. Lo que puede hacer es seleccionar el size del size desde el frente y luego intercambiar cada uno en el conjunto de muestreo con otra posición en él. Por lo tanto, si permite el reemplazo, se mezclará cada vez más.

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

Este algoritmo tiene solo 2*size pasos de 2*size , si incluye el método de slice , para seleccionar la muestra aleatoria.

Más aleatorio

Para hacer que la muestra sea más aleatoria, podemos seleccionar al azar el punto de inicio de la muestra. Pero es un poco más caro obtener la muestra.

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

Lo que hace que esto sea más aleatorio es el hecho de que cuando siempre baratas los artículos de frente, no los consigues con mucha frecuencia en la muestra si la matriz de muestreo es grande y la muestra es pequeña. Esto no sería un problema si no se supone que la matriz sea siempre la misma. Entonces, lo que hace este método es cambiar esta posición donde comienza la región mezclada.

Sin reemplazo

Para no tener que copiar la matriz de muestreo y no preocuparse por el reemplazo, puede hacer lo siguiente, pero le da un 3*size frente al 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;
}

Sin reemplazo y más aleatorio

Para aplicar el algoritmo que dio un poco más muestras aleatorias a la función sin reemplazo:

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

Más rápido...

Al igual que todas estas publicaciones, usa la mezcla aleatoria de Fisher-Yates. Pero, eliminé el exceso de copiar la matriz.

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

Answer 7

Si usa lodash, la API cambió en 4.x:

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

https://lodash.com/docs#sampleSize

Answer 8

Si bien apoyo firmemente el uso de Fisher-Yates Shuffle, como lo sugiere Tim Down , aquí hay un método muy breve para lograr un subconjunto aleatorio según lo solicitado, matemáticamente correcto, incluido el conjunto vacío, y el conjunto dado en sí.

La solución de nota depende de lodash / guión bajo :

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