Выборка случайного подмножества из массива

Я предлагаю перетасовать копию массива, используя перетасовку Фишера-Йейтса и беру кусочек:

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

Обратите внимание, что это будет не самый эффективный метод для получения небольшого случайного подмножества большого массива, поскольку он излишне перемешивает весь массив. Для лучшей производительности вы можете вместо этого сделать частичное перемешивание:

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

Немного поздно для вечеринки, но это можно решить с помощью нового метода подчеркивания sample (подчеркивание 1.5.2 - сентябрь 2013 г.):

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

var randomFiveNumbers = _.sample(x, 5);

Или... если вы используете underscore.js...

_und = require('underscore');

...

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

Достаточно просто.

На мой взгляд, я не считаю необходимым тасовать всю колоду. Вам просто нужно убедиться, что ваш образец случайный, а не ваша колода. Что вы можете сделать, так это выбрать количество size спереди, а затем поменять местами каждое из них в массиве выборки с другой позицией в нем. Итак, если вы разрешаете замену, вы все больше и больше перемешиваете.

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

Этот алгоритм состоит всего из 2*size шагов, если вы включите метод slice для выбора случайной выборки.

Больше случайных

Чтобы сделать выборку более случайной, мы можем случайным образом выбрать начальную точку выборки. Но это немного дороже, чтобы получить образец.

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

Что делает это более случайным, так это тот факт, что, когда вы всегда просто перетасовываете первые элементы, вы, как правило, не очень часто получаете их в выборке, если массив выборки велик, а выборка мала. Это не было бы проблемой, если бы массив не должен был всегда быть одним и тем же. Итак, что делает этот метод, так это изменяет эту позицию, где начинается перетасованный регион.

Нет замены

Чтобы не копировать массив выборки и не беспокоиться о замене, вы можете сделать следующее, но это даст вам 3*size против 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;
}

Нет замены и больше случайных

Чтобы применить алгоритм, который давал немного больше случайных выборок, к функции без замены:

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

Быстрее...

Как и во всех этих сообщениях, здесь используется перетасовка Фишера-Йейтса. Но я удалил накладные расходы на копирование массива.

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

Хотя я решительно поддерживаю перетасовку Фишера-Йейтса, как предложено Тимом Дауном, вот очень короткий метод для получения случайного подмножество по запросу, математически правильное, включая пустое множество и само заданное множество.

Примечание Решение зависит от lodash / подчеркивание:

Лодаш v4

const _ = require('loadsh')

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

Лодаш v3

const _ = require('loadsh')

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

Если вы используете lodash, API изменился в 4.x:

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

https://lodash.com/docs#sampleSize

Возможно, я что-то упускаю, но, похоже, есть решение, которое не требует сложности или потенциальных накладных расходов на перетасовку:

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

Вы можете получить образец из 5 элементов следующим образом:

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

Вы можете определить его как функцию для использования в вашем коде:

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

Или добавьте его в сам объект Array:

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

если вы хотите, вы можете разделить код на две функции (перемешать и сэмплировать):

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

Вы можете удалить элементы из копии массива по мере их выбора. Производительность, вероятно, не идеальна, но может подойти для того, что вам нужно:

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

Вот еще одна реализация, основанная на Shuffle Фишера-Йейтса. Но этот оптимизирован для случая, когда размер выборки значительно меньше длины массива. Эта реализация не сканирует весь массив и не выделяет массивы такого размера, как исходный массив. Он использует разреженные массивы для уменьшения выделения памяти.

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

Многие из этих ответов говорят о клонировании, перетасовке, нарезке исходного массива. Мне было любопытно, почему это помогает с точки зрения энтропии/распределения.

Я не эксперт, но я написал пробную функцию, используя индексы, чтобы избежать каких-либо мутаций массива — хотя она добавляется к набору. Я также не знаю, как происходит случайное распределение, но код был достаточно простым, чтобы, я думаю, дать ответ здесь.

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 = [
  'confused', 'astonishing', 'mint', 'engine', 'team', 'cowardly', 'cooperative',
  'repair', 'unwritten', 'detailed', 'fortunate', 'value', 'dogs', 'air', 'found',
  'crooked', 'useless', 'treatment', 'surprise', 'hill', 'finger', 'pet',
  'adjustment', 'alleged', 'income'
];

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

Для очень больших массивов эффективнее работать с индексами, а не с членами массива.

Вот к чему я пришел после того, как не нашел ничего, что мне понравилось на этой странице.

/**
 * Get a random subset of an array
 * @param {Array} arr - Array to take a smaple of.
 * @param {Number} sample_size - Size of sample to pull.
 * @param {Boolean} return_indexes - If true, return indexes rather than members
 * @returns {Array|Boolean} - An array containing random a subset of the members or 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]);
}