是否可以使用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>';