10 ответов:
таким образом, с каждым элементом хранить число, которое отмечает его относительную вероятность, например, если у вас есть 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)); } }
- генерировать равномерно распределенные случайные числа.
- перебирайте свой список до тех пор, пока суммарная вероятность посещенных элементов не будет больше, чем случайное число
пример кода:
double p = Math.random(); double cumulativeProbability = 0.0; for (Item item : items) { cumulativeProbability += item.probability(); if (p <= cumulativeProbability) { return item; } }
представьте, что у нас есть следующий список
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 попадает в диапазон элемента В.
mj
вы можете попробовать Выбор Колеса Рулетки.
сначала сложите все вероятности, затем масштабируйте все вероятности в масштабе 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 (включительно), тогда вы можете сделать решение как и выше.
алгоритм, описанный в Ушман это,Брент!--3--> и ответы @kaushaya реализованы в Apache commons-math библиотека.
посмотри EnumeratedDistribution класс (заводной код следует):
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 - это будет автоматически нормализуется.
мой метод довольно прост. Сгенерируйте случайное число. Теперь, поскольку вероятности ваших элементов известны, просто повторите сортированный список вероятностей и выберите элемент, вероятность которого меньше случайно сгенерированного числа.
для получения более подробной информации,прочитайте мой ответ здесь.
медленный, но простой способ сделать это-иметь каждый член, чтобы выбрать случайное число на основе его вероятности и выбрать тот, который имеет наибольшее значение.
аналогия:
представьте, что 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.
ответ Брента это хорошо, но это не учитывает возможность ошибочного выбора элемента с вероятностью 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; } }
Если вы не возражаете добавить зависимость от третьей стороны в свой код, вы можете использовать MockNeat.вероятности() метод.
например:
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();отказ от ответственности: я являюсь автором библиотеки, поэтому я могу быть предвзятым, когда я рекомендую его.
вы можете использовать код 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эта функция эффективно возвращает индекс элемента.
Comments