例如：有一个数组包含四个项目，我想随机获取其中一个，如下所示：
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
]
如何在Javascript中选择加权随机数组元素？
33
- Geza
1
4可能是 Generate A Weighted Random Number 的重复问题。 - Bill the Lizard
8个回答
71
上面的两个答案都依赖于会很快变慢的方法，尤其是被接受的那个。
这是一个函数，它只需要两个相同长度的列表，items和weights，并根据weights中对应的选择概率从items中随机选择一个项目。weights数组应该是非负数，但不需要总和为特定值，并且可以处理非整数权重。
我在2020年12月将我的旧ES6解决方案替换为这个，因为旧浏览器不支持ES6，并且我个人认为这个更易读。
如果您更喜欢使用具有属性“item”和“weight”的对象：
如果一个随机数正好落在两个权重的边界上，比如图示中的7和15，我们选择较长的那个。这是因为0可以被Math.random选择到，但1不能，所以我们得到了一个公平的分布。如果我们选择较短的那个，A可能会被选择6次（0、1、2、3、4）中的任意一次，这会使它的权重高于它应该有的权重。
这是一个函数，它只需要两个相同长度的列表，items和weights，并根据weights中对应的选择概率从items中随机选择一个项目。weights数组应该是非负数，但不需要总和为特定值，并且可以处理非整数权重。
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;
}
解释：
我制作了这个图表，展示了这个工作原理：
如果一个随机数正好落在两个权重的边界上，比如图示中的7和15，我们选择较长的那个。这是因为0可以被Math.random选择到，但1不能，所以我们得到了一个公平的分布。如果我们选择较短的那个，A可能会被选择6次（0、1、2、3、4）中的任意一次，这会使它的权重高于它应该有的权重。
- Radvylf Programs
26
8你可能想澄清一下“答案 #2”是什么。答案按票数排序，因此它们的顺序可能会改变。人们还可以按其他方式对答案进行排序（例如，按最早的先后顺序）。 - JJJ
1@Envayo 没有区别。它基于权重的总和，因此您可以按任何比例缩放它。 - Radvylf Programs
1@LovelyWeather89 你可以使用一个
for循环倒序遍历数组，检查i（for循环变量）是否等于items.indexOf(items[i])。如果不是，则表示i处的项是重复的。然后，您只需要将任何非重复项及其权重.push到空数组中。类似于这样的东西。 - Radvylf Programs1@LovelyWeather89 对不起，我的错误，
i++ 应该改为 i--，而 > 应该改为 >=。如果你只想在普通数组中删除重复项，而不是在这个答案中使用的 items/weights，你可以使用 Array.from(new Set(x))，其中 x 是要从中删除重复项的数组。 - Radvylf Programs1@dmikester1 他们不需要加起来等于任何特定的数值，这将把它们相加并将其作为分母。例如，如果你有权重为
1、4和0.5的选项，它们分别有18.2%、72.7%和9.1%的概率被选择。 - undefined显示剩余21条评论
8
使用一些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;
- Paul Walczewski
1
2请确保您的值已按概率排序。 - O'Neill
1
这里有一个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";
}
还记得这个来自小学的数学原理吗？“指定分布中的所有数字在随机选择时有相等的概率。”
这告诉我们，在特定范围内，无论这个范围有多大或多小，每个随机数字都有相等的概率出现。
就是这样。应该可以了！
- John Doe
1
ES2015版本的Radvylf Programs的答案
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)];
}
- Georgiy Bukharov
1
这里有一种比其他答案提供的更快的方法...
你可以通过以下方式实现你想要的：
1. 根据每个元素的概率（例如，具有60％概率的元素将占据60％的段），将0到1段分成各个部分。
2. 生成一个随机数，并检查它落在哪个部分。 步骤1 为概率数组制作前缀和数组，其中每个值表示其相应部分的结束位置。
例如：如果我们有概率值：60％（0.6），30％，5％，3％，2％。则前缀和数组将是：
以下是如何实现此方法的方式：
你可以通过以下方式实现你想要的：
1. 根据每个元素的概率（例如，具有60％概率的元素将占据60％的段），将0到1段分成各个部分。
2. 生成一个随机数，并检查它落在哪个部分。 步骤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!');
希望这对你有所帮助。
注意：
（在计算机科学中）列表/数组中一个值的下限是大于或等于该值的最小元素。例如，数组：[1,10,24,99]和值12。下限将是值为24的元素。
当数组按从小到大排序时（就像我们的情况一样），可以通过二分查找（O(log(n))）非常快地找到每个值的下限。
- atanay
3
很抱歉，这很有帮助，但您能否也提供一个使用它的例子呢？ - Jon
代码不按照定义的概率返回 - 我运行了十万次，得到了0个普通，5990个罕见，25144个稀有等结果。 - Jon
开头的0不是键的一部分，它表示59900个常见项，25144个不常见项等。 - atanay
0
我添加了我的解决方案作为一个方法，在较小的数组上运行良好（无缓存）：
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);
- Mitzi
0
最近我遇到了这个问题，并通过使用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];
}
}
您可以随意更改这些值，但要点是，switch 会从1到10随机生成一个数字，而cases会确定el3有10％的几率（1/10），el2有20％的几率，并且对于cases 1-7，el1是获胜者（70％）。
如果您想在较大的数组中加权一系列数组元素，则可以让case运行另一个随机数以从范围中选择，而不是返回固定元素。例如：
...
case 1:
case 2:
case 3:
return array[randNum(0, rangeMax)];
- Writhyn
-2
当然可以。这里是一个简单的代码来实现它：
// 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.
- Noobit
2
5这对于小整数来说效果相当不错（这也是我的使用情况），但由于它通过创建一个长度等于权重总和的新数组来实现，所以对于大数字来说可能会变得很大/缓慢。而且它也不适用于非整数，因此您需要找到最小公倍数才能得到整数（对于非常精确的权重可能无法实现）。 - mattsoave
3@mattsoave 是的，这个已经比第二个答案慢了几千倍，而且还有五个选项。 - Radvylf Programs
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接