Как выбрать предмет по его вероятности?

Ответ 1

Таким образом, каждый элемент хранит число, которое отмечает его относительную вероятность, например, если у вас есть 3 элемента, вы должны быть в два раза чаще, чем один из двух других, тогда ваш список будет иметь:

 [{A,1},{B,1},{C,2}]

Затем суммируем номера списка (т.е. 4 в нашем случае). Теперь создайте случайное число и выберите этот индекс. int index = rand.nextInt(4); верните число, чтобы индекс находился в правильном диапазоне.

Код Java:

class Item {
    int relativeProb;
    String name;

    //Getters Setters and Constructor
}

...

class RandomSelector {
    List<Item> items = new List();
    Random rand = new Random();
    int totalSum = 0;

    RandomSelector() {
        for(Item item : items) {
            totalSum = totalSum + item.relativeProb;
        }
    }

    public Item getRandom() {

        int index = rand.nextInt(totalSum);
        int sum = 0;
        int i=0;
        while(sum < index ) {
             sum = sum + items.get(i++).relativeProb;
        }
        return items.get(Math.max(0,i-1));
    }
}

Ответ 2

• Создать равномерно распределенное случайное число.
• Итерируйте по списку, пока кумулятивная вероятность посещенных элементов больше, чем случайное число.

Пример кода:

double p = Math.random();
double cumulativeProbability = 0.0;
for (Item item : items) {
    cumulativeProbability += item.probability();
    if (p <= cumulativeProbability) {
        return item;
    }
}

Ответ 3

притворимся, что у нас есть следующий список

Item A 25%
Item B 15%
Item C 35%
Item D 5%
Item E 20%

Давайте сделаем вид, что все вероятности являются целыми числами и присваивают каждому элементу "диапазон", который вычисляется следующим образом.

Start - Sum of probability of all items before
End - Start + own probability

Новые числа выглядят следующим образом

Item A 0 to 25
Item B 26 to 40
Item C 41 to 75
Item D 76 to 80
Item E 81 to 100

Теперь выберите случайное число от 0 до 100. Предположим, вы выбрали 32. 32 попадает в диапазон предметов B.

MJ

Ответ 4

Вы можете попробовать Выбор колеса рулетки.

Сначала добавьте все вероятности, затем масштабируйте все вероятности в масштабе 1, разделив каждый на сумму. Предположим, что вероятности A(0.4), B(0.3), C(0.25) and D(0.05). Затем вы можете создать случайное число с плавающей запятой в диапазоне [0, 1]. Теперь вы можете решить следующее:

random number between 0.00 and 0.40 -> pick A
              between 0.40 and 0.70 -> pick B
              between 0.70 and 0.95 -> pick C
              between 0.95 and 1.00 -> pick D

Вы также можете сделать это со случайными целыми числами - скажем, вы генерируете случайное целое число от 0 до 99 (включительно), тогда вы можете принять решение, как указано выше.

Ответ 5

Алгоритм, описанный в ответах Ushman's, Brent и @kaushaya, реализован в библиотека Apache commons-math.

Взгляните на EnumeratedDistribution class (groovy code следует):

def probabilities = [
   new Pair<String, Double>("one", 25),
   new Pair<String, Double>("two", 30),
   new Pair<String, Double>("three", 45)]
def distribution = new EnumeratedDistribution<String>(probabilities)
println distribution.sample() // here you get one of your values

Обратите внимание, что сумма вероятностей не должна быть равна 1 или 100 - она ​​будет автоматически нормализована.

Ответ 6

Мой метод довольно прост. Создайте случайное число. Теперь, поскольку вероятности ваших предметов известны, просто перебирайте отсортированный список вероятности и выбирайте элемент, вероятность которого меньше, чем случайное число.

Подробнее см. мой ответ здесь.

Ответ 7

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

Аналогия:

Представьте, что нужно выбрать 1 из 3 человек, но они имеют разные вероятности. Вы даете им умереть с разным количеством лиц. У первого лица кости есть 4 лица, 2-й человек 6 и третий человек 8. Они бросают свою кубик, а побеждает тот, у кого наибольшее количество побед.

Допустим, у нас есть следующий список:

[{A,50},{B,100},{C,200}]

псевдокод:

 A.value = random(0 to 50);
 B.value = random(0 to 100);
 C.value = random (0 to 200);

Мы выбираем тот, который имеет наибольшее значение.

Этот метод выше точно не отображает вероятности. Например, 100 не будут иметь вдвое больше шансов на 50. Но мы можем сделать это, немного изменив метод.

Метод 2

Вместо того, чтобы выбирать число от 0 до веса, мы можем ограничить их от верхнего предела предыдущей переменной до добавления текущей переменной.

[{A,50},{B,100},{C,200}]

псевдокод:

 A.lowLimit= 0; A.topLimit=50;
 B.lowLimit= A.topLimit+1; B.topLimit= B.lowLimit+100
 C.lowLimit= B.topLimit+1; C.topLimit= C.lowLimit+200 

конечные пределы

A.limits = 0,50
B.limits = 51,151
C.limits = 152,352

Затем мы выбираем случайное число от 0 до 352 и сравниваем его с каждым переменным пределом, чтобы увидеть, находится ли случайное число в его пределах.

Я считаю, что эта настройка имеет лучшую производительность, поскольку есть только 1 случайное поколение.

В других ответах есть аналогичный метод, но этот метод не требует, чтобы сумма составляла 100 или 1.00.

Ответ 8

Брент-ответ хорош, но он не учитывает возможность ошибочного выбора элемента с вероятностью 0 в случаях, когда p = 0. Это достаточно легко справиться, проверяя вероятность (или, возможно, не добавляя элемент в первую очередь):

double p = Math.random();
double cumulativeProbability = 0.0;
for (Item item : items) {
    cumulativeProbability += item.probability();
    if (p <= cumulativeProbability && item.probability() != 0) {
        return item;
    }
}

Ответ 9

Вы можете использовать код Julia:

function selrnd(a::Vector{Int})
    c = a[:]
    sumc = c[1]
    for i=2:length(c)
        sumc += c[i]
        c[i] += c[i-1]
    end
    r = rand()*sumc
    for i=1:length(c)
        if r <= c[i]
            return i
        end
    end
end

Эта функция эффективно возвращает индекс элемента.