Первый способ
Берём рандомный элемент из массива
Генерируем случайное число в промежутке [0, 100]
Если вероятность элемента больше чем сгенерированное число, то включаем его в наш массив
const items = [{
id: 1,
name: 'Item 1',
odds: 0.1
}, {
id: 2,
name: 'Item 2',
odds: 0.75
}, {
id: 3,
name: 'Item 3',
odds: 2.15
}, {
id: 4,
name: 'Item 4',
odds: 17
}, {
id: 5,
name: 'Item 5',
odds: 80
}];
const getRandomItems = (items, count) => {
const randomItems = [];
while (randomItems.length !== count) {
const randomIndex = Math.floor(Math.random() * items.length);
const randomItem = items[randomIndex];
const includeChance = Math.random() * 100;
if (randomItem.odds >= includeChance) randomItems.push(randomItem.name);
}
return randomItems;
}
console.log(getRandomItems(items, 32));
У этого алгоритма есть недостаток: Он может работать потенциально очень долго, т.к. не понятно когда массив заполнится
Второй способ (смотрите в UPD на исправленную версию)
Генерируем случайное число в промежутке [0, 100]
Гуляем по массиву и смотрим у кого из элементов веротяность появления больше чем у сгенерированного числа
Кто первый попался того и включаем в наш массив
const items = [{
id: 1,
name: 'Item 1',
odds: 0.1
}, {
id: 2,
name: 'Item 2',
odds: 0.75
}, {
id: 3,
name: 'Item 3',
odds: 2.15
}, {
id: 4,
name: 'Item 4',
odds: 27
}, {
id: 5,
name: 'Item 5',
odds: 70
}];
const getRandomItems = (items, count) => {
const randomItems = [];
while(count !== 0) {
let includeChance = Math.random() * 100;
for (const item of items) {
if (includeChance < item.odds) {
randomItems.push(item.name);
--count;
break;
}
}
}
return randomItems;
}
console.log(getRandomItems(items, 32));
У этого алгоритма сложность будет равна count * items.length
У этого алгоритма есть недостаток: Если будут 2 элемента с вероятностями по 50, то всегда будет включён, тот кто первый. Чтобы устранить этот недостаток было предложено использовать накопительные суммы вероятностей, но пока я не очень понимаю что это такое не буду вписывать в свой алгоритм
UPD
Я наконец-то осознал как работают "накопительные суммы вероятностей" :) Попробую объяснить на простых примерах
Обозначения:
- НП - Наибольший Полуинтервал -
[0, 100)
- СЧ - это случайное Сгенерированное Число в пределах НП
Начнём с самой проблемы, как мы уже увидели что если у нас 2 элемента с вероятностями по 50, то всегда будет выбираться первый. Но на самом деле это только верхушка проблемы, в общем проблема в том что второй алгоритм будет включать ВСЕГДА только первый элемент сруди тех у кого одинаковые вероятнсти. Например пусть у нас есть следующие вероятности [1, 1, 2, 2, 3, 3, 4, 4, 80]
, тогда если случайным образом нам выпадет число 1/2/3/4
, то в результирующем массиве мы получим только первые 1/2/3/4
, а вторые не будут включены никогда. Схематически это можно изобразить так:

Выбираем случайную точку на отрезке - это и будет нашим СЧ. Далее проводим вертикальную прямую от этой точки и смотрим с каким прямоугольником прямая пересечётся первой, этот прямоугольник и есть элемент, который мы добавим в массив. Теперь ясно видно, почему вторые (другие равные) прямоугльники не будут включены никогда
По схеме мы явно видим и вторую проблему: если СЧ будет больше чем максимально возможная вероятность (в схеме это 80), то мы не добавим ничего в наш массив. Было бы хорошо покрыть весь НП, чтобы при любом значении СЧ мы что-то добавляли в массив. Таким образом нам нужно добиться того чтобы схема выглядела так:

Во второй схеме явно видно, что:
- при любом значении СЧ мы что-то добавим в наш массив
- у каждого элемента теперь есть шанс попасть в массив, независимо от того где он находился в исходном массиве, т.к. мы покрываем все значение из НП
- каждый из элементов занимает, пропорциональный своей вероятности, полуинтервал
Глядя на вторую схему, легко понять каким полуинтервалам принадлежит тот или иной прямоугольник:
1 - [0, 1)
1 - [1, 2)
2 - [2, 4)
2 - [4, 6)
3 - [6, 9)
3 - [9, 12)
4 - [12, 16)
4 - [16, 20)
80 - [20, 100)
В таком подходе есть ещё один очень важный плюс: Если например у нас будут вероятности [1, 1, 1, 1, 1, 95]
, то шанс попадания одного из элементов с вероятностью 1 в 5 раз больше чем при первом подходе. Но это не значит что они обязательно будут включены в массив. Дело вот в чём, они попадут в массив, если
- количество требуемых элементов достаточно велико
- метод генерирующий случайные числа выдаёт их, в заданном полуинтервале, равномерно. Например нам нужны 1000 СЧ в НП, то не будет такой картины, что числа после 50 выпадают заметно чаще чем до него или что отдельные взятые полуинтервалы к примеру
[25, 50)
и [75, 100]
имеют больший шанс, что СЧ будет принадлежать им
Если количество требуемых элементов не велико, то вероятность попадания одного из элементов с низкой вероятностью уменьшается
Если не гарантируется равномерность, то каким бы большим числом не было количество требуемых элементов, будет НЕнулевая вероятность того, что некоторые элементы никогда не попадут в массив
Если же не выполняются оба условия, то можете считать, что никогда не увидите в массиве элементы с низким шансом
Так что есть немало факторов, кроме самих подходов, которые влияют не результат. "в 5 раз" - может показаться большой разницей, но это тоже зависит от исходных данных, например пусть вероятности [0.1, 0.1, 0.1, 0.1, 0.1, 99,5]
, тогда что 0.1
что 0.5
почти не будет играть роли
Чтобы понять как запрограммировать второй подход, вышеописанные полуинтервалы нужно переписать в следующем виде:
1 - [0, 0 + 1)
1 - [0 + 1, 0 + 1 + 1)
2 - [0 + 1 + 1, 0 + 1 + 1 + 2)
2 - [0 + 1 + 1 + 2, 0 + 1 + 1 + 2 + 2)
3 - [0 + 1 + 1 + 2 + 2, 0 + 1 + 1 + 2 + 2 + 3)
3 - [0 + 1 + 1 + 2 + 2 + 3, 0 + 1 + 1 + 2 + 2 + 3 + 3)
4 - [0 + 1 + 1 + 2 + 2 + 3 + 3, 0 + 1 + 1 + 2 + 2 + 3 + 3 + 4)
4 - [0 + 1 + 1 + 2 + 2 + 3 + 3 + 4, 0 + 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4)
80 - [0 + 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4, 0 + 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 80)
Отсюда видно, что в правой части - то что в левой части + вероятность текущего элемента
Теперь перед нами стоит задача: Понять какому из промежутков принадлежит СЧ. Т.к. мы не можем сразу с ходу ответить на этот вопрос, то нам придётся начиная перебирать полуинтервалы начиная с первого
И так пусть СЧ - это x
, и чтобы понять принадлежит ли x
полуинтервалу [a, b)
, нам надо убедиться что выполняется a <= x < b
:
0 <= x < 0 + 1
- отнимаем (0)
=> 0 - (0) <= x - (0) < 0 + 1 - (0)
=> 0 <= x - (0) < 1
, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
0 + 1 <= x < 0 + 1 + 1
- отнимаем ((0) + 1)
=> 0 + 1 - ((0) + 1) <= x - ((0) + 1) < 0 + 1 + 1 - ((0) + 1)
=> 0 <= x - ((0) + 1) < 1
, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
0 + 1 + 1 <= x < 0 + 1 + 1 + 2
- отнимаем (((0) + 1) + 1)
=> 0 + 1 + 1 - (((0) + 1) + 1) <= x - (((0) + 1) + 1) < 0 + 1 + 1 + 2- (((0) + 1) + 1)
=> 0 <= x - (((0) + 1) + 1) < 2
, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
и т.д. пока не дойдём до последнего. Но этот алгоритм можно упростить, заметив следующее:
для упрощения мы всегда отнимаем левую часть у всех частей неравенства. Оно и логично, ведь как мы заметили раньше, правая часть - это левая часть + вероятность текущего элемента, а значит можно не пересчитывать два раза одно и то же
после упрощений слева всегда остаётся 0
сравнивать 0 <= СЧ
бессмысленно, т.к. изначально СЧ принимает значения [0, 100)
, потому всё что нам надо - это сравнивать СЧ с правой частью полуинтервала
для каждого нового полуинтервала мы сначала отнимаем, то что отнимали в предыдущих шагах. Зачем? Мы можем не тратить время на повторные вычисления
У первого интервала всегда левая часть будет 0
, потому его можно не писать и не учитывать при вычислениях. Тогда наши полуинтервалы будут выглядеть так:
1 - [0, 1)
1 - [1, 1 + 1)
2 - [1 + 1, 1 + 1 + 2)
и т.д. думаю смысл ясен
Учитывая замечания, предыдущий алгоритм можно выполнять так:
x < 1
, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
x < 1 + 1
- отнимаем 1
(правая часть предыдущего полуинтервала) => x - (1) < 1
, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
x - (1) < 1 + 1 + 2 - (1)
- откуда появился - (1)
у правой части? Мы уже уменьшили на предыдущем шаге наш x
, а значит при следующем сравнении, правая часть так же должна быть уменьшена на то же значение, на сколько мы уменьшили x
- должны были отнимать (1 + 1)
, но мы уже 1 единицу отсюда отняли на предыдущем шаге, потому по сути надо просто отнять (1 + 1) - 1 = 1
=> x - (1 + 1) < 1 + 2 - 1
=> x - 1 - 1 < 2
, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
x - (1 + 1) < 1 + 1 + 2 + 2 - (1 + 1)
=> x - (1 + 1) < 2 + 2
- отнимаем 2
=> x - (1 + 1 + 2) < 2
, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
x - (1 + 1 + 2) < 1 + 1 + 2 + 2 + 3 - (1 + 1 + 2)
=> x - (1 + 1 + 2) < 2 + 3
- отнимаем 2
=> x - (1 + 1 + 2 + 2) < 3
, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
x - (1 + 1 + 2 + 2) < 1 + 1 + 2 + 2 + 3 + 3 - (1 + 1 + 2 + 2)
=> x - (1 + 1 + 2 + 2) < 3 + 3
- отнимаем 3
=> x - (1 + 1 + 2 + 2 + 3) < 3
, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
x - (1 + 1 + 2 + 2 + 3) < 1 + 1 + 2 + 2 + 3 + 3 + 4 - (1 + 1 + 2 + 2 + 3)
=> x - (1 + 1 + 2 + 2) < 3 + 4
- отнимаем 3
=> x - (1 + 1 + 2 + 2 + 3 + 3) < 4
, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
x - (1 + 1 + 2 + 2 + 3 + 3) < 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 - (1 + 1 + 2 + 2 + 3 + 3)
=> x - (1 + 1 + 2 + 2 + 3 + 3) < 4 + 4
- отнимаем 4
=> x - (1 + 1 + 2 + 2 + 3) < 4
, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
x - (1 + 1 + 2 + 2 + 3 + 3 + 4) < 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 80 - (1 + 1 + 2 + 2 + 3 + 3 + 4)
=> x - (1 + 1 + 2 + 2 + 3 + 3 + 4) < 4 + 80
- отнимаем 4
=> x - (1 + 1 + 2 + 2 + 3 + 3 + 4 + 4) < 80
, если мы дошли до последнего шага, то значит последний элемент будет очевидно включён
Для простоты записи давайте заменим x - (...)
на x_(номер шага)
, тогда это всё можно записать в очень простом виде:
x_1 < 1
x_2 < 1
x_3 < 2
x_4 < 2
x_5 < 3
x_6 < 3
x_7 < 4
x_8 < 4
x_9 < 80
, где каждый x_n
- можно выразить через предыдущий
Если внимательно посмотреть на правую сторону, то мы увидим что там остались ровно те вероятности, которые были изначально у элементов. Теперь у нас есть всё, чтобы запрограммировать это:
Второй способ (исправленный)
const items = [{
id: 1,
name: 'Item 1',
odds: 0.1
}, {
id: 2,
name: 'Item 2',
odds: 0.75
}, {
id: 3,
name: 'Item 3',
odds: 2.15
}, {
id: 4,
name: 'Item 4',
odds: 27
}, {
id: 5,
name: 'Item 5',
odds: 70
}];
const getRandomItems = (items, count) => {
const randomItems = [];
while(count !== 0) {
let includeChance = Math.random() * 100;
for (const item of items) {
if (includeChance < item.odds) {
randomItems.push(item.name);
--count;
break;
}
includeChance -= item.odds;
}
}
return randomItems;
}
console.log(getRandomItems(items, 32));
Примеры для наглядности разницы работы первого и второго алгоритма:
const getRandomItems1 = (items, count) => {
const randomItems = [];
while(count !== 0) {
let includeChance = Math.random() * 100;
for (const item of items) {
if (includeChance < item.odds) {
randomItems.push(item.name);
--count;
break;
}
}
}
return randomItems;
}
const getRandomItems2 = (items, count) => {
const randomItems = [];
while(count !== 0) {
let includeChance = Math.random() * 100;
for (const item of items) {
if (includeChance < item.odds) {
randomItems.push(item.name);
--count;
break;
}
includeChance -= item.odds;
}
}
return randomItems;
}
const items1 = [{
id: 1,
name: 'Item 1',
odds: 50
}, {
id: 2,
name: 'Item 2',
odds: 50
}];
console.log(JSON.stringify(getRandomItems1(items1, 16))); // Только 'Item 1'
console.log(JSON.stringify(getRandomItems2(items1, 16)));
console.log('----------------------------------------');
const items2 = [{
id: 1,
name: 'Item 1',
odds: 20
}, {
id: 2,
name: 'Item 2',
odds: 20
}, {
id: 3,
name: 'Item 3',
odds: 30
}, {
id: 4,
name: 'Item 4',
odds: 30
}];
console.log(JSON.stringify(getRandomItems1(items2, 16))); // Только 'Item 1' и/или 'Item 3'
console.log(JSON.stringify(getRandomItems2(items2, 16)));
console.log('----------------------------------------');
const items3 = [{
id: 1,
name: 'Item 1',
odds: 1
}, {
id: 2,
name: 'Item 2',
odds: 1
}, {
id: 3,
name: 'Item 3',
odds: 1
}, {
id: 4,
name: 'Item 4',
odds: 1
}, {
id: 5,
name: 'Item 5',
odds: 1
}, {
id: 6,
name: 'Item 6',
odds: 95
}];
console.log(JSON.stringify(getRandomItems1(items3, 16))); // Только 'Item 1' и/или 'Item 6'
console.log(JSON.stringify(getRandomItems2(items3, 16)));
Для меня самым интересным во всём этом является то, что разница между кодом первого и второго алгоритмов - это всего одна строчка includeChance -= item.odds
, а за этим стоит целая теория :)