从数组中采样随机子集

Question

什么是采用随机样本的简洁方法,而无需在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)];

但如果这样做多次,则存在多次抓取相同条目的风险.

Answer 1

我建议使用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);
}

Answer 2

派对有点晚了,但这可以通过下划线的新样本 方法解决(下划线1.5.2 - 2013年9月):

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

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

Answer 3

您可以通过以下方式获得 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 个功能（随机播放和示例）：

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

Answer 4

或者......如果你使用underscore.js ......

_und = require('underscore');

...

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

很简单.

Answer 5

虽然我强烈支持按照 Tim Down 的建议使用 Fisher-Yates Shuffle，但这里有一个非常简短的方法，用于根据要求实现随机子集，数学上正确，包括空集和给定集本身。

注意解决方案取决于lodash / underscore：

洛达什 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));
}

Answer 6

在我看来，我认为没有必要洗整整个套牌。你只需要确保你的样本是随机的，而不是你的牌组。您可以做的是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;
}

快点...

像所有这些帖子一样，这使用了 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 = [];