是否可以使用 Array.prototype.reduce 创建数组的线性随机选择？

Question

使用 Array.prototype.reduce（或 Array.prototype.reduceRight）的签名，是否有可能 select 数组中的一项对所有索引具有相同的概率？这是我的尝试：

document.write(`
${[...'abcdefghijklmnopqrstuvwxyz'].reduce(function(last, next, index, array) {
  if (Math.random() > index / array.length) {
    return next;
  }

  return last;
})}
`);

对此进行了几次测试后，分布似乎偏向较低的指数（也就是说较高的指数 selected 的频率更高）。

Answer 1

您可以为此使用 reservoir sampling：始终 select 第一个元素，然后在遍历数组时，将当前 select 的项目替换为 k^th（基于 1 的索引）项，概率为 1/k。这会给你一个均匀的概率：

document.write(`
${[...'abcdefghijklmnopqrstuvwxyz'].reduce(function(last, next, index, array) {
  if ( Math.random()*(index + 1) <= 1 ) {
    return next;
  }

  return last;
})}
`);

这里有一个测试来证明它 return 每个字母的概率是一致的：

var results = {};
for ( var i = 0; i < 100000; i++ ) {
    var choice = [...'abcdefghijklmnopqrstuvwxyz'].reduce(function(last, next, index, array) {
        if ( Math.random()*(index + 1) <= 1 ) {
            return next;
        }

        return last;
    } );
    results[ choice ] = (results[ choice ] || 0) + 1;
}

document.body.innerHTML = '<pre>' + JSON.stringify( results, '\t' ) + '</pre>';

是否可以使用 Array.prototype.reduce 创建数组的线性随机选择？

Is it possible to create a linearly random selection of an array using Array.prototype.reduce?

javascript

arrays

reduce

random-sample