Выбор случайного объекта на основе вероятностей
Существует подобный вопрос, я знаю, но он смутил меня, таким образом, я думал это легче спросить в моем пути.
Таким образом, у меня есть массив значений, положительных и отрицательных. Чем выше они, тем больше вероятности они имеют того, чтобы быть выбранным.
Я испытываю затруднения, на самом деле выясняющие, как присвоить вероятности и затем случайным образом выбрать ту. Я предполагаю, что массив должен будет быть отсортирован сначала, но затем я немного потерян после этого.
2 ответа
"У меня есть чашки для кофе разных размеров. Чем они больше, тем больше я хочу за них брать. Мне трудно понять, как назначить цены".
Это не просто проблема программирования - вы указали, что вероятность увеличивается с ростом стоимости, но не сказали, как она увеличивается с ростом стоимости. Обычно в кофейнях не берут плату прямо пропорционально количеству кофе. Вы не можете назначить вероятности пропорционально ценности, потому что некоторые из ваших ценностей отрицательны, а вероятности не могут быть отрицательными.
Похоже, вам нужно еще немного разобраться в проблеме, прежде чем писать код.
Если вам действительно не важно, как вероятность связана со значением, кроме того, что они увеличиваются в порядке возрастания значения, то один простой способ:
- отсортируйте ваш массив
- присвойте вероятность 1 первому элементу, 2 - второму и так далее.
- теперь ваши вероятности не складываются в 1, что является проблемой. Поэтому разделите каждую вероятность на сумму всех вероятностей, которые вы присвоили:
(1 + 2 + ... + n) = n(n+1)/2. Это называется "нормализацией".
Учитывая ваш список вероятностей, которые в сумме дают 1, самый простой способ многократно выбрать одну из них - это вычислить кумулятивную вероятность, что я продемонстрирую на примере:
value (sorted): -12 -3 127 1000000
assigned probability: 0.1 0.2 0.3 0.4
cumulative probability: 0.1 0.3 0.6 1.0
Кумулятивная вероятность определяется как сумма всех вероятностей до этого момента.
Итак, от генератора случайных чисел вам нужно случайное значение (с плавающей точкой) между 0 и 1. Если оно лежит между 0 и 0,1, вы выбрали -12. Если оно лежит между 0,1 и 0,3, вы выбрали -3, и так далее. Чтобы выяснить, в каком диапазоне оно находится, можно пройти линейно по массиву или выполнить двоичный поиск.
При желании можно пропустить шаг нормализации и использование плавающей точки. Назначьте "кумулятивные вероятности" (1, 3, 6, 10 ...), но дайте понять, что фактическая вероятность - это сохраненное целочисленное значение, деленное на n(n+1)/2. Затем выберите случайное целое число от 0 до n(n+1)/2 - 1. Если оно меньше 1, вы выбрали первое значение, если меньше 3 - второе, и так далее. Это может сделать код более понятным, а может и не сделать, и ваш ГПСЧ может хорошо или плохо справляться с выбором целочисленных значений из большого диапазона.
Обратите внимание, что вы могли бы назначить вероятности (0.001, 0.002, 0.003, 0.994) вместо (0.1, 0.2, 0.3, 0.4), и при этом удовлетворить требование "чем больше значение, тем выше вероятность".
Один из способов:
- Сделать все значения положительными (добавить абсолютное значение минимального значения ко всем значениям)
- Нормализовать значения суммировать до 1 (разделить каждое значение на сумму значений)
Теперь, чтобы рандомизировать значение из сгенерированного распределения, вы можете
- Выбрать случайное число на [0,1].
- Начните суммировать вероятности, пока сумма не станет больше или равна случайному значению. Выберите этот индекс в качестве случайного значения.