logo标签列表

从数组中抽取一个随机子集

javascriptarraysrandomnumerical-methods
35

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

但如果这样做多次，有重复获取相同条目的风险。

我注意到 Avi Moondra 的 bl.ock 使用了这种技术。 - Nate Anderson
15个回答
62

我建议使用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);
}
1
underscore.js使用Fisher-Yates洗牌算法的“现代版本”（https://github.com/jashkenas/underscore/blob/ffabcd443fd784e4bc743fff1d25456f7282d531/underscore.js#L361） - davidDavidson
应该使用i * Math.random()而不是(i + 1) * Math.random()。Math.random() * (i + 1)在Math.floor后可能会返回i。当i == arr.length时，arr [i]将导致索引越界。 - Aaron Zorel
@AaronJo：不，这是有意的。当计算index时，i已经被减少了，因此在第一次迭代中，第一个函数中的i + 1等于arr.length，这是正确的。 - Tim Down
对于那些已经在使用 d3 的人，可以从 d3-array 模块中导入 shuffle。它也使用了 Fisher-Yates shuffle。详情见下文。 - NicoWheat
21

虽然略微晚了些，但这个问题可以使用underscore新的sample方法（underscore 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);
1
这只为我生成了1个元素，而不是5个。 - Snowman
从 underscore 的文档中得知："从列表中生成一个随机样本。传递一个数字以返回列表中的 n 个随机元素。否则将返回单个随机项。" - 你是否传入了第二个参数？ - alengel
3
lodash拥有一个_.sampleSize函数，其功能如上所述：https://lodash.com/docs/4.17.4#sampleSize - tonyg
@alengel 是的。我传递了第二个参数（在我的情况下是20），并获得了1个输出。 - Rylan Schaeffer
当我尝试运行你上面的代码时，randomFiveNumbers 是一个单独的整数。 - Rylan Schaeffer
7

我认为，洗整副牌并不是必要的。你只需要确保你的样本是随机的，而不是你的牌组。你可以从前面选择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 = [];
7
您可以通过以下方式获得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); };
1
简化：Array(15).fill(0).map((_,i)=> i+1).sort((a,b) => Math.random()-0.5).slice(0,5) - Max Murphy
5

虽然我强烈支持使用Fisher-Yates洗牌算法，正如Tim Down所建议的，但这里有一种非常简短的方法来实现一个随机子集，数学上是正确的，包括空集和给定的集合本身。

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

Lodash v4

const _ = require('loadsh')

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

Lodash v3

const _ = require('loadsh')

function subset(arr) {
    return _.sample(arr, _.random(arr.length));
}
被踩了。这个答案不起作用。应该是 _.sampleSize(arr, _.random(arr.length - 1))。 - Manan Mehta
5
@MananMehta 虽然让作者知道你为什么点踩肯定是更好的，所以感谢你这样做，但下次请考虑给作者更新一个五年前的回答的机会。当这篇文章写出来时，Lodash V4还不存在，而对于V3仍然正确。无论如何，我添加了一个关于V4的回答。 - Selfish
5

或者……如果您使用underscore.js……

_und = require('underscore');

...

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

简单明了。

3
3
很多回答都涉及到克隆、洗牌、切片原始数组。我很好奇从熵/分布角度来看这些方法是如何有帮助的。
虽然我不是专家，但我写了一个使用索引避免任何数组突变的示例函数——它确实会添加到 Set 中。我也不知道这个方法的随机分布性如何，但我认为代码足够简单，值得在这里得到解答。 

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

2

这里是基于Fisher-Yates 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;
}
我不知道这是如何工作的，但它确实更有效率，当 count << array.length。为了使其完全通用（即，当 count 等于或大于数组长度时），我添加了以下内容：` let val = array[indices[j] === undefined ? j : indices[j]]; if (val === undefined) { result.length = i; break; } result[i] = val;以强制 result.length <= array.length，否则将在结果中得到一堆undefined`。 - Moos
2
也许我有所遗漏，但似乎有一种解决方案不需要洗牌的复杂性或潜在开销：
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;
}
我同意：如果size很小，我想这是最快的解决方案。 - Sylvain Lesage
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接