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

Question

У меня есть список предметов. Каждый из этих предметов имеет свою вероятность.

Кто-нибудь может предложить алгоритм выбора предмета на основе его вероятности?

Answer 1

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

Пример кода:

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

Answer 2

Таким образом, для каждого элемента хранится число, обозначающее его относительную вероятность, например, если у вас есть 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));
    }
}

Answer 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

Answer 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 (включительно), тогда вы можете принять решение, как указано выше.

Answer 5

Алгоритм описан в Ответы Ушмана , Брента и @ kaushaya реализованы в Apache commons-math library.

Взгляните на EnumeratedDistribution class (следует простой код):

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 - она ​​будет нормализована автоматически.

Answer 6

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

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

Answer 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.

Answer 8

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

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

Answer 9

Если вы не против добавления сторонней зависимости в ваш код, вы можете использовать метод MockNeat.probabilities () .

Например:

String s = mockNeat.probabilites(String.class)
                .add(0.1, "A") // 10% chance to pick A
                .add(0.2, "B") // 20% chance to pick B
                .add(0.5, "C") // 50% chance to pick C
                .add(0.2, "D") // 20% chance to pick D
                .val();

Отказ от ответственности: я являюсь автором библиотеки, поэтому я могу быть предвзятым, когда рекомендую ее.

Answer 10

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

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

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