Псевдослучайный алгоритм выбора полуслучайного элемента в массиве

Question

У меня есть простой массив (или набор, если вы предпочитаете) целых чисел, назовем его X. У меня также есть другой массив W, который хранит «вес» элементов в массиве X. «Вес» указывает, насколько вероятно n-Этот элемент должен быть выбран.Теперь мне нужен метод (алгоритм) для (псевдо) случайного выбора одного элемента из массива / набора X в соответствии с его «весом», определенным в массиве W.

Например, если мой W выглядит так: W [0] = 2;W [1] = 4;W [2] = 6;

, что означает вероятность выбора N-го элемента из массива X: X [0] = 16,6% X [1] = 33,3% X [2] = 50%

, поэтому метод get_pseudorandom_item (X) должен возвращать 2-й элемент примерно в половине случаев.

Любые идеи или предложения по реализации этого (на любом языке программирования) высоко ценятсяСпасибо.

Answer 1

1. Создать массив P с частичными суммами весов, т.е.

   ( P ₀ = W ₀ ), ( P ₁ = Ш ₀ + Ш ₁ ), ..., ( P _n = Ш ₀ + Ш ₁ + ... + Ш _п )

   (вы можете сделать это в течение W , на самом деле, если вам впоследствии не понадобятся веса).

2. Генерация случайного числа r в [0, P _n ), где P _n обозначает последнюю такую ​​сумму (т. Е. Сумму всех весов).

3. Найдите индекс k из наименьшей (первой) частичной суммы больше , чем сгенерированное вами число:

   P _k > r & # x2003; & и; & # x2003; &для всех; a <<em> k : P _a <<em> r

4. Используйте этот индекс для выбора фактического элемента: X _k

Answer 2

Для каждого типа объекта x [i] Где y - это вес. Добавьте y элементов в массив типа x [i].

Затем выберите из этого массива случайным образом.

Если взять ваш пример, у вас будет 2 Вт [0], 4 Вт [1] и 6 Вт [2] в коллекции, из которой вы случайным образом выбираете предмет типа 0, 1 или 2.

Answer 3

Предположим, что числа в X[] составляют в сумме 1,0.Поэтому X[2] будет 0.5000.

. Вы выбираете свой номер и добавляете его до тех пор, пока не «закончите случайно».

Вот пример Java:

double rand = random.nextDouble();
double sofar = 0.0;

for(int i = 0; i < X.length; x++) {
    if(sofar + X[i] > rand) return W[i];
    sofar += X[i];
}
throw new IllegalStateException("Numbers add up to less than 1");

Answer 4

Первое, что приходит мне в голову, это не очень красивое решение, но я все равно поделюсь им!

Вы можете создать другой массив (скажем, с 100 целыми числами). Каждое целое число будет представлять индекс в W . На основании указанного процента вы можете заполнить этот массив целыми числами.

Так что если у вас есть X [0] = 25% X [1] = 25% X [2] = 50% Массив будет иметь 25 1, 25 2 и 50 3

Затем вы можете выбрать псевдослучайный индекс этого массива и использовать возвращенный индекс для извлечения объекта в W .

Как я уже сказал, это безобразно, но это сработало бы:)