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

Question

使用Array.prototype.reduce（或Array.prototype.reduceRight）的签名，是否可以从所有索引中以相同概率从数组中选择一个项目？这里是我的尝试：

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

 
    return last; 
 
})} 
 
`);

做的这几个测试运行后，分配似乎对指数较低被扭曲（这是说，上指数往往选择） 。

Answer 1

可以使用reservoir sampling此：始终选择第一个元素，那么，你通过阵列迭代，替换当前已经与k个^选择第（基于1的索引）项目的项，与1/k概率。这会给你一个统一的概率：

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

    return last; 
})} 
`); 

下面是测试证明，它并返回每个字母有一个统一的概率：

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