Что такое чистый способ получения случайной выборки без замены массива в javascript? Предположим, что существует массив
x = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
и я хочу случайным образом выбрать 5 уникальных значений; т.е. создать случайное подмножество длины 5. Для генерации одной случайной выборки можно было бы сделать что-то вроде:
x[Math.floor(Math.random()*x.length)];
Но если это делается несколько раз, существует риск захвата одной и той же записи несколько раз.
Я предлагаю перетасовать копию массива, используя Fisher-Yates shuffle и взяв фрагмент:
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);
}
Достаточно просто.
Вы можете удалить элементы из копии массива по мере их выбора. Производительность, вероятно, не идеальна, но это может быть хорошо для того, что вам нужно:
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;
}
В то время как я решительно поддерживаю использование Fisher-Yates Shuffle, как предложенный Тимом Дауном, здесь очень короткий метод для получения случайного подмножества по запросу, математически правильный, включая пустые множества и заданный набор.
Примечание: решение зависит от lodash/underscore:
function subset(arr) {
return _.sample(arr, _.random(arr.length));
}
По-моему, я не думаю, что нужно перетасовать всю колоду. Вам просто нужно убедиться, что ваш образец случайный, а не ваша колода. Что вы можете сделать, это выбрать сумму 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 vs 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;
}
Как и все эти сообщения, это использует Fisher-Yates Shuffle. Но я удалил над головой копирование массива.
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, API изменился в 4.x:
const oneItem = _.sample(arr);
const nItems = _.sampleSize(arr, n);
Вот еще одна реализация, основанная на Fisher-Yater 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;
}
Вы можете получить образец из 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]); };
если вы хотите, вы можете разделить код, чтобы иметь 2 функции (Shuffle и 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); };
Возможно, я что-то упускаю, но, похоже, есть решение, которое не требует сложности или потенциальных издержек при перемешивании:
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;
}