如何在JavaScript中选择加权随机数组元素?

sqyvllje  于 2023-04-28  发布在  Java
关注(0)|答案(8)|浏览(144)

**例如:**数组中有四个元素。我想随机得到一个,像这样:

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
]
kknvjkwl

kknvjkwl1#

上面的两个答案都依赖于很快变慢的方法,尤其是被公认的方法。

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,我个人认为这个解决方案更具可读性。
如果您更愿意使用具有属性itemweight的对象:

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]的输入时会发生什么。通过取权重的部分和,你只需要找到第一个和随机数一样大的,那就是随机选择的项目。
如果在两个权重的边界上选择一个随机数,如图中的715,我们选择较长的一个。这是因为0可以被Math.random选择,而1不能,所以我们得到了一个公平的分布。如果我们使用较短的一个,A可以在18次中选择6次(01234),使其具有比应有的更高的权重。

mrzz3bfm

mrzz3bfm2#

一些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;
zpgglvta

zpgglvta3#

这里有一个更快的方法,然后其他答案建议。..
你可以通过以下方式实现你想要的:
1.基于每个元素的概率将0到1的段划分为每个元素的部分(例如,概率为60%的元素将占据段的60%)。
1.生成随机数并检查它落在哪个段中。

第一步

为概率数组做一个前缀和数组,其中的每个值将表示其对应部分的结束位置。

例如:如果我们有概率:60%(0.6)、30%、5%、3%、2%。前缀和数组将是:[0.6,0.9,0.95,0.98,1]

我们将有一个这样的分段(近似):[ | | ||]

步骤2

在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!');

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

oprakyz7

oprakyz74#

这里有一个O(1)(常数时间)算法来解决你的问题。
生成一个从0到99的随机数(总共100个数字)。如果在给定的子范围内有40个数字(0到39),那么随机选择的数字将有40%的概率落在这个范围内。代码如下:

const number = Math.floor(Math.random() * 99); // 0 to 99
let element;

if (number >= 0 && number <= 39) {
    // 40% chance that this code runs. Hence, it is a bike.
    element = "bike";
}

else if (number >= 40 && number <= 69) {
    // 30% chance that this code runs. Hence, it is a car.
    element = "car";
}

else if (number >= 70 && number <= 84) {
    // 15% chance that this code runs. Hence, it is a boat.
    element = "boat";
}

else if (number >= 85 && number <= 94) {
    // 10% chance that this code runs. Hence, it is a train.
    element = "train";
}

else if (number >= 95 && number <= 99) {
    // 5% chance that this code runs. Hence, it is a plane.
    element = "plane";
}

还记得这个吗,一个小学的数学原理?“一个特定分布中的所有数字都有相等的概率被随机选择。”
这告诉我们,每个随机数在特定范围内出现的概率相等,无论该范围有多大或小。
就这样。应该可以了!

cdmah0mi

cdmah0mi5#

我添加了我的解决方案,作为一个在较小数组上工作良好的方法(没有缓存):

static weight_random(arr, weight_field){
    
        if(arr == null || arr === undefined){
            return null;
        }
        const totals = [];
        let total = 0;
        for(let i=0;i<arr.length;i++){
            total += arr[i][weight_field];
            totals.push(total);
        }
        const rnd = Math.floor(Math.random() * total);
        let selected = arr[0];
        for(let i=0;i<totals.length;i++){
            if(totals[i] > rnd){
                selected = arr[i];
                break;
            }
        }
    return selected;

}

像这样运行它(提供数组和权重属性):

const wait_items =  [
    {"w" : 20, "min_ms" : "5000", "max_ms" : "10000"},
    {"w" : 20, "min_ms" : "10000", "max_ms" : "20000"},
    {"w" : 20, "min_ms" : "40000", "max_ms" : "80000"}
]   

const item = weight_random(wait_items, "w");
console.log(item);
ltqd579y

ltqd579y6#

ES2015版本Radvylf Programs's answer

function getWeightedRandomItem(items) {
    const weights = items.reduce((acc, item, i) => {
        acc.push(item.weight + (acc[i - 1] || 0));
        return acc;
    }, []);
    const random = Math.random() * weights[weights.length - 1];
    return items[weights.findIndex((weight) => weight > random)];
}

ES2022

function getWeightedRandomItem(items) {
    const weights = items.reduce((acc, item, i) => {
        acc.push(item.weight + (acc[i - 1] ?? 0));
        return acc;
    }, []);
    const random = Math.random() * weights.at(-1);
    return items[weights.findIndex((weight) => weight > random)];
}
yxyvkwin

yxyvkwin7#

我最近遇到了这个问题,并使用switch case解决了它,这很有帮助,因为您可以为每个元素分配多个“case”,从而对它们进行加权。
我有一个简单的,常见的随机数函数,我运行它的随机性:

const array = [el1, el2, el3];

const getWeightedElement = () => {
        switch (randNum(1, 10)) {
            case 10:
                return array[2];
            case 8:
            case 9:
                return array[1];
            default:
                return array[0];
        }
    }

您可以随意更改这些值,但要点是开关从1到10滚动一个随机数,并且情况确定el 3有10%的机会(1/10),el 2有20%的机会,并且对于情况1-7,el 1是赢家(70%)。
如果你想在一个更大的数组中加权一个数组元素的范围,你可以让case运行另一个随机数来从 range 中挑选,而不是返回一个固定的元素。即

...
case 1:
case 2:
case 3:
    return array[randNum(0, rangeMax)];
gkn4icbw

gkn4icbw8#

你当然可以这里有一个简单的代码来做这件事:

// Object or Array. Which every you prefer.
var item = {
    bike:40, // Weighted Probability
    care:30, // Weighted Probability
    boat:15, // Weighted Probability
    train:10, // Weighted Probability
    plane:5 // Weighted Probability
    // The number is not really percentage. You could put whatever number you want.
    // Any number less than 1 will never occur
};

function get(input) {
    var array = []; // Just Checking...
    for(var item in input) {
        if ( input.hasOwnProperty(item) ) { // Safety
            for( var i=0; i<input[item]; i++ ) {
                array.push(item);
            }
        }
    }
    // Probability Fun
    return array[Math.floor(Math.random() * array.length)];
}

console.log(get(item)); // See Console.

相关问题