Intereting Posts

Выбор случайного элемента на основе вероятностей

Есть такой же вопрос , я знаю, но это меня смутило, поэтому мне было легче спросить на моем пути.

Поэтому у меня есть массив значений, положительный и отрицательный. Чем выше они, тем больше вероятность их выбора.
У меня возникли проблемы с тем, чтобы определить, как назначать вероятности, а затем произвольно выбирать их. Я предполагаю, что массив нужно будет отсортировать первым, но потом я немного потерял после этого.

    «У меня разные чашки кофе различного размера: чем больше они, тем больше я хочу их взимать. У меня возникают проблемы с тем, как правильно определять цены».

    Это не просто проблема программирования – вы указали, что вероятность увеличивается со значением, но вы не сказали, как она увеличивается со значением. Обычно кофейни не заряжаются прямо пропорционально количеству кофе. Вы не можете назначать вероятности пропорционально стоимости, потому что некоторые из ваших значений отрицательны, но вероятности не могут быть отрицательными.

    Похоже, вам нужно немного приглушить проблему, прежде чем писать код.

    Если вам действительно все равно, как вероятность относится к значению, кроме того, что они увеличиваются в порядке стоимости, тогда один простой способ:

    • сортировать массив
    • назначить вероятность 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 секунд и так далее. Это может или не может сделать код более четким, и ваш RNG может или не может наилучшим образом выбирать целочисленные значения из большого диапазона.

    Обратите внимание, что вы могли назначить вероятности (0,001, 0,002, 0,003, 0,994) вместо (0,1, 0,2, 0,3, 0,4) и все еще удовлетворяли вашему требованию, чтобы «чем выше значение, тем выше вероятность».

    Одним из способов может быть

    • Сделать все значения положительными (добавить абсолютное значение минимального значения ко всем значениям)
    • Нормализовать значения до суммы до 1 (делить каждое значение с суммой значений)

    Чтобы рандомизировать значение из сгенерированного распределения, теперь вы можете

    • Выберите случайное число на [0,1].
    • Начните суммирование вероятностей до тех пор, пока сумма не станет больше или не будет равна случайной величине. Выберите этот индекс как свое случайное значение.

    Следуя предложению Стива Джессопа, после того, как вы выбрали случайное целое число от 0 до n (n + 1) / 2 – 1, вы можете просто получить треугольный корень: (-1 + sqrt ((8 * x) +1 )) / 2