如何在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

这里有一个比其他答案更快的方法。。。

您可以通过以下方式实现您想要的：

1. 根据每个元素的概率将0到1段划分为部分（例如，概率为60%的元素将占用60%的段）。
2. 生成一个随机数并检查它落在哪个段。

第一步

为概率数组创建一个前缀和数组，其中的每个值将表示其相应部分的结束位置。

例如：如果我们有概率：60%（0.6），30%，5%，3%，2%。前缀和数组将是：[0.6,0.9,0.95,0.98,1]

所以我们将有一个这样（近似）划分的部分：[| | | |]

第二步

生成一个介于0和1之间的随机数，并在前缀和数组中找到它的下限。您将找到的索引是随机数到达的段的索引

以下是实现此方法的方法：

let obj = {
    "Common": "60",
    "Uncommon": "25",
    "Rare": "10",
    "Legendary": "0.01",
    "Mythical": "0.001"
}
// turning object into array and creating the prefix sum array:
let sums = [0]; // prefix sums;
let keys = [];
for(let key in obj) {
    keys.push(key);
    sums.push(sums[sums.length-1] + parseFloat(obj[key])/100);
}
sums.push(1);
keys.push('NONE');
// Step 2:
function lowerBound(target, low = 0, high = sums.length - 1) {
    if (low == high) {
        return low;
    }
    const midPoint = Math.floor((low + high) / 2);
  
    if (target < sums[midPoint]) {
        return lowerBound(target, low, midPoint);
    } else if (target > sums[midPoint]) {
        return lowerBound(target, midPoint + 1, high);
    } else {
        return midPoint + 1;
    }
}

function getRandom() {
    return lowerBound(Math.random());
}

console.log(keys[getRandom()], 'was picked!');

希望这对你有所帮助。注：（在计算机科学中）列表/数组中值的下限是大于或等于它的最小元素。例如，数组：[1,10,24,99]和值12。下限将是值为24的元素。当数组从最小到最大排序时（就像我们的例子），通过二进制搜索（O（log（n）），可以非常快地找到每个值的下界。

Answer 2

一些es6方法，带有通配符处理：

const randomizer = (values) => {
    let i, pickedValue,
            randomNr = Math.random(),
            threshold = 0;

    for (i = 0; i < values.length; i++) {
        if (values[i].probability === '*') {
            continue;
        }

        threshold += values[i].probability;
        if (threshold > randomNr) {
                pickedValue = values[i].value;
                break;
        }

        if (!pickedValue) {
            //nothing found based on probability value, so pick element marked with wildcard
            pickedValue = values.filter((value) => value.probability === '*');
        }
    }

    return pickedValue;
}

示例用法：

let testValues = [{
    value : 'aaa',
    probability: 0.1
},
{
    value : 'bbb',
    probability: 0.3
},
{
    value : 'ccc',
    probability: '*'
}]

randomizer(testValues); // will return "aaa" in 10% calls, 
//"bbb" in 30% calls, and "ccc" in 60% calls;

Answer 3

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

function weighted_random(items, weights) {
    var i;

    for (i = 0; i < weights.length; i++)
        weights[i] += weights[i - 1] || 0;
    
    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，我个人认为这个更具可读性。

如果您更愿意使用属性为项和重量的对象：

function weighted_random(options) {
    var i;

    var weights = [];

    for (i = 0; i < options.length; i++)
        weights[i] = options[i].weight + (weights[i - 1] || 0);
    
    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。随机但是1不能，所以我们得到了一个公平的分布。如果我们选择较短的一个，A可以在18次选择中选择6次（0，1，2，3，4），赋予它更高的权重。