javascript - 如何在 Javascript 中选择加权随机数组元素？

Question

例如:一个数组中有四个项目。我想随机得到一个，像这样:

array items = [
    "bike"    //40% chance to select
    "car"     //30% chance to select
    "boat"    //15% chance to select
    "train"   //10% chance to select
    "plane"   //5%  chance to select
]

Answer 1

以上两个答案都依赖于会很快变慢的方法，尤其是公认的方法。

function weighted_random(items, weights) {
    var i;

    for (i = 1; i < weights.length; i++)
        weights[i] += weights[i - 1];
    
    var random = Math.random() * weights[weights.length - 1];
    
    for (i = 0; i < weights.length; i++)
        if (weights[i] > random)
            break;
    
    return items[i];
}

自 2020 年 12 月起，我用这个解决方案替换了我的旧 ES6 解决方案，因为旧浏览器不支持 ES6，我个人认为这个解决方案更具可读性。

如果您更愿意使用具有属性 item 和 weight 的对象:

function weighted_random(options) {
    var i;

    var weights = [options[0].weight];

    for (i = 1; i < options.length; i++)
        weights[i] = options[i].weight + weights[i - 1];
    
    var random = Math.random() * weights[weights.length - 1];
    
    for (i = 0; i < weights.length; i++)
        if (weights[i] > random)
            break;
    
    return options[i].item;
}

解释:

我制作了这张图表来展示它是如何工作的:

此图显示了当输入权重为 [5, 2, 8, 3] 时会发生什么。通过对权重进行部分求和，您只需找到第一个与随机数一样大的权重，即随机选择的项目。

如果在两个权重的边界上选择了一个随机数，如图中的 7 和 15，我们会选择较长的一个。这是因为 0 可以被 Math.random 选择，而 1 不能，所以我们得到了公平的分配。如果我们选择较短的那个，A 可以在 18 次中选择 6 次(0、1、2, 3, 4), 赋予它比应有的更高的权重。