Случайное число с вероятностями

Ответ 1

У вас уже неплохой путь и хорошо работает с любым диапазоном.

Просто подумайте: еще одна возможность - избавиться от фракций, умножив их на постоянный множитель, а затем построить массив с размером этого множителя. Умножая на 10, вы получаете

P(1) = 2
P(2) = 3
P(3) = 5

Затем вы создаете массив с обратными значениями - "1" переходит в элементы 1 и 2, "2" в 3-6 и так далее:

P = (1,1, 2,2,2, 3,3,3,3,3);

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

(Добавить.) Используя вероятности из примера в комментарии kiruwka:

int[] numsToGenerate           = new int[]    { 1,   2,    3,   4,    5   };
double[] discreteProbabilities = new double[] { 0.1, 0.25, 0.3, 0.25, 0.1 };

наименьший множитель, который приводит к целым целым, равен 20, что дает вам

2, 5, 6, 5, 2

и поэтому длина numsToGenerate будет равна 20, со следующими значениями:

1 1
2 2 2 2 2
3 3 3 3 3 3
4 4 4 4 4
5 5

Распределение точно такое же: вероятность "1", например, теперь равна 2 из 20 - еще 0,1.

Это основано на ваших первоначальных вероятностях, добавляющих до 1. Если они этого не делают, умножьте общее на этот же коэффициент (который также будет вашей длиной массива).

Ответ 2

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

public class DistributedRandomNumberGenerator {

    private HashMap<Integer, Double> distribution;
    private double distSum;

    public DistributedRandomNumberGenerator() {
        distribution = new HashMap<>();
    }

    public void addNumber(int value, double distribution) {
        if (this.distribution.get(value) != null) {
            distSum -= this.distribution.get(value);
        }
        this.distribution.put(value, distribution);
        distSum += distribution;
    }

    public int getDistributedRandomNumber() {
        double rand = Math.random();
        double ratio = 1.0f / distSum;
        double tempDist = 0;
        for (Integer i : distribution.keySet()) {
            tempDist += distribution.get(i);
            if (rand / ratio <= tempDist) {
                return i;
            }
        }
        return 0;
    }

}

Использование класса выглядит следующим образом:

    public static void main(String[] args) {
        DistributedRandomNumberGenerator drng = new DistributedRandomNumberGenerator();
        drng.addNumber(1, 0.2d);
        drng.addNumber(2, 0.3d);
        drng.addNumber(3, 0.5d);

        int testCount = 1000000;

        HashMap<Integer, Double> test = new HashMap<>();

        for (int i = 0; i < testCount; i++) {
            int random = drng.getDistributedRandomNumber();
            test.put(random, (test.get(random) == null) ? (1d / testCount) : test.get(random) + 1d / testCount);
        }

        System.out.println(test.toString());
    }

Пример вывода для этого тестового драйвера:

{1=0.20019100000017953, 2=0.2999349999988933, 3=0.4998739999935438}

Ответ 3

Вы уже написали реализацию в своем вопросе.;)

final int ran = myRandom.nextInt(100);
if (ran > 50) { return 3; }
else if (ran > 20) { return 2; } 
else { return 1; }

Вы можете ускорить это для более сложных реализаций за счет вычисления результата в таблице коммутаторов следующим образом:

t[0] = 1; t[1] = 1; // ... one for each possible result
return t[ran];

Но это следует использовать, только если это узкое место производительности и называется несколько сотен раз в секунду.

Ответ 4

Если у вас есть проблема производительности, а не поиск всех n значений O (n)

вы можете выполнить бинарный поиск, который стоит O (log n)

Random r=new Random();      
double[] weights=new double[]{0.1,0.1+0.2,0.1+0.2+0.5};
// end of init
double random=r.nextDouble();
// next perform the binary search in weights array

вам нужно всего лишь получить доступ к log2 (weights.length) в среднем, если у вас много элементов веса.

Ответ 5

Ваш подход подходит для конкретных выбранных вами номеров, хотя вы можете уменьшить объем хранилища, используя массив из 10 вместо массива из 100. Однако этот подход не очень хорошо обобщает на большое количество результатов или результатов с вероятностями таких как 1/e или 1/PI.

Потенциально лучшим решением является использование таблицы псевдонимов. Метод alias использует O(n) для настройки таблицы для результатов n, но тогда это постоянное время для генерации независимо от того, сколько результатов существует.