Генератор случайных чисел с распределенной вероятностью
Я хочу создать число, основанное на распределенной вероятности. Например, просто скажите, что есть следующие вхождения чисел:
Number| Count
1 | 150
2 | 40
3 | 15
4 | 3
with a total of (150+40+15+3) = 208
then the probability of a 1 is 150/208= 0.72
and the probability of a 2 is 40/208 = 0.192
Как создать генератор случайных чисел, который возвращает числа на основе этого распределения вероятностей?
Я доволен тем, что на данный момент он основан на статическом жестком коде, но в конечном итоге я хочу, чтобы он получил распределение вероятности из запроса к базе данных.
Я видел похожие примеры, такие как этот, но они не очень общие. Любые предложения?
Ответы
Ответ 1
Общий подход состоит в том, чтобы подавать равномерно распределенные случайные числа из интервала 0..1 в обратную функцию кумулятивного распределения вашего желаемого распределения.
Таким образом, в вашем случае просто нарисуйте случайное число x из 0..1 (например, Random.NextDouble()
) и на основе его Возврат значения
- 1, если 0 <= x < 150/208,
- 2, если 150/208 <= x < 190/208,
- 3, если 190/208 <= x < 205/208 и
- 4 в противном случае.
Ответ 2
Этот вопрос объясняет различные подходы к генерации случайных чисел с различными вероятностями. Согласно этой статье, показанной на этом вопросе, лучшим подобным подходом (с точки зрения временной сложности) является так называемый "метод псевдонимов", Майкл Вось.
Для вашего удобства я написал и предоставил здесь реализацию С# генератора случайных чисел, реализующего метод псевдонимов:
public class LoadedDie {
// Initializes a new loaded die. Probs
// is an array of numbers indicating the relative
// probability of each choice relative to all the
// others. For example, if probs is [3,4,2], then
// the chances are 3/9, 4/9, and 2/9, since the probabilities
// add up to 9.
public LoadedDie(int probs){
this.prob=new List<long>();
this.alias=new List<int>();
this.total=0;
this.n=probs;
this.even=true;
}
Random random=new Random();
List<long> prob;
List<int> alias;
long total;
int n;
bool even;
public LoadedDie(IEnumerable<int> probs){
// Raise an error if nil
if(probs==null)throw new ArgumentNullException("probs");
this.prob=new List<long>();
this.alias=new List<int>();
this.total=0;
this.even=false;
var small=new List<int>();
var large=new List<int>();
var tmpprobs=new List<long>();
foreach(var p in probs){
tmpprobs.Add(p);
}
this.n=tmpprobs.Count;
// Get the max and min choice and calculate total
long mx=-1, mn=-1;
foreach(var p in tmpprobs){
if(p<0)throw new ArgumentException("probs contains a negative probability.");
mx=(mx<0 || p>mx) ? p : mx;
mn=(mn<0 || p<mn) ? p : mn;
this.total+=p;
}
// We use a shortcut if all probabilities are equal
if(mx==mn){
this.even=true;
return;
}
// Clone the probabilities and scale them by
// the number of probabilities
for(var i=0;i<tmpprobs.Count;i++){
tmpprobs[i]*=this.n;
this.alias.Add(0);
this.prob.Add(0);
}
// Use Michael Vose alias method
for(var i=0;i<tmpprobs.Count;i++){
if(tmpprobs[i]<this.total)
small.Add(i); // Smaller than probability sum
else
large.Add(i); // Probability sum or greater
}
// Calculate probabilities and aliases
while(small.Count>0 && large.Count>0){
var l=small[small.Count-1];small.RemoveAt(small.Count-1);
var g=large[large.Count-1];large.RemoveAt(large.Count-1);
this.prob[l]=tmpprobs[l];
this.alias[l]=g;
var newprob=(tmpprobs[g]+tmpprobs[l])-this.total;
tmpprobs[g]=newprob;
if(newprob<this.total)
small.Add(g);
else
large.Add(g);
}
foreach(var g in large)
this.prob[g]=this.total;
foreach(var l in small)
this.prob[l]=this.total;
}
// Returns the number of choices.
public int Count {
get {
return this.n;
}
}
// Chooses a choice at random, ranging from 0 to the number of choices
// minus 1.
public int NextValue(){
var i=random.Next(this.n);
return (this.even || random.Next((int)this.total)<this.prob[i]) ? i : this.alias[i];
}
}
Пример:
var loadedDie=new LoadedDie(new int[]{150,40,15,3}); // list of probabilities for each number:
// 0 is 150, 1 is 40, and so on
int number=loadedDie.nextValue(); // return a number from 0-3 according to given probabilities;
// the number can be an index to another array, if needed
Я размещаю этот код в общедоступном домене.
Ответ 3
Сделайте это только один раз:
- Напишите функцию, которая вычисляет массив cdf с учетом массива PDF. В вашем примере массив pdf [150,40,15,3], массив cdf будет [150, 190, 205, 208].
Делайте это каждый раз:
- Получите случайное число в [0,1], умножьте на 208, усечь вверх (или вниз: я оставлю его вам, чтобы подумать об угловых случаях). У вас будет целое число в 1..208. Назовите его r.
- Выполните двоичный поиск в cdf-массиве для r. Верните индекс ячейки, содержащей r.
Время работы будет пропорционально log размера данного массива pdf. И это хорошо. Однако, если размер вашего массива всегда будет таким маленьким (4 в вашем примере), то выполнение линейного поиска будет проще, а также будет работать лучше.
Ответ 4
Спасибо всем вашим ребятам! Очень ценим!
@Menjaraz Я попытался реализовать ваше решение, поскольку оно выглядит очень дружелюбным к ресурсам, однако с некоторыми трудностями с синтаксисом.
Итак, теперь я просто преобразовал сводку в плоский список значений, используя LINQ SelectMany() и Enumerable.Repeat().
public class InventoryItemQuantityRandomGenerator
{
private readonly Random _random;
private readonly IQueryable<int> _quantities;
public InventoryItemQuantityRandomGenerator(IRepository database, int max)
{
_quantities = database.AsQueryable<ReceiptItem>()
.Where(x => x.Quantity <= max)
.GroupBy(x => x.Quantity)
.Select(x => new
{
Quantity = x.Key,
Count = x.Count()
})
.SelectMany(x => Enumerable.Repeat(x.Quantity, x.Count));
_random = new Random();
}
public int Next()
{
return _quantities.ElementAt(_random.Next(0, _quantities.Count() - 1));
}
}
Ответ 5
Я знаю, что это старый пост, но я также искал такой генератор и не был удовлетворен решениями, которые я нашел. Поэтому я написал свои собственные и хочу поделиться им с миром.
Просто позвоните "Добавить (...)" несколько раз, прежде чем вы вызовете "NextItem (...)"
/// <summary> A class that will return one of the given items with a specified possibility. </summary>
/// <typeparam name="T"> The type to return. </typeparam>
/// <example> If the generator has only one item, it will always return that item.
/// If there are two items with possibilities of 0.4 and 0.6 (you could also use 4 and 6 or 2 and 3)
/// it will return the first item 4 times out of ten, the second item 6 times out of ten. </example>
public class RandomNumberGenerator<T>
{
private List<Tuple<double, T>> _items = new List<Tuple<double, T>>();
private Random _random = new Random();
/// <summary>
/// All items possibilities sum.
/// </summary>
private double _totalPossibility = 0;
/// <summary>
/// Adds a new item to return.
/// </summary>
/// <param name="possibility"> The possibility to return this item. Is relative to the other possibilites passed in. </param>
/// <param name="item"> The item to return. </param>
public void Add(double possibility, T item)
{
_items.Add(new Tuple<double, T>(possibility, item));
_totalPossibility += possibility;
}
/// <summary>
/// Returns a random item from the list with the specified relative possibility.
/// </summary>
/// <exception cref="InvalidOperationException"> If there are no items to return from. </exception>
public T NextItem()
{
var rand = _random.NextDouble() * _totalPossibility;
double value = 0;
foreach (var item in _items)
{
value += item.Item1;
if (rand <= value)
return item.Item2;
}
return _items.Last().Item2; // Should never happen
}
}
Ответ 6
Используйте мой метод. Это просто и легко понять.
Я не считаю часть в диапазоне 0... 1, я просто использую "Probabilityp Pool" (звучит круто, да?)
На круговой диаграмме вы можете увидеть вес каждого элемента в пуле
Здесь вы можете увидеть реализацию накопительной вероятности для рулетки
`
// Some c`lass or struct for represent items you want to roulette
public class Item
{
public string name; // not only string, any type of data
public int chance; // chance of getting this Item
}
public class ProportionalWheelSelection
{
public static Random rnd = new Random();
// Static method for using from anywhere. You can make its overload for accepting not only List, but arrays also:
// public static Item SelectItem (Item[] items)...
public static Item SelectItem(List<Item> items)
{
// Calculate the summa of all portions.
int poolSize = 0;
for (int i = 0; i < items.Count; i++)
{
poolSize += items[i].chance;
}
// Get a random integer from 0 to PoolSize.
int randomNumber = rnd.Next(0, poolSize) + 1;
// Detect the item, which corresponds to current random number.
int accumulatedProbability = 0;
for (int i = 0; i < items.Count; i++)
{
accumulatedProbability += items[i].chance;
if (randomNumber <= accumulatedProbability)
return items[i];
}
return null; // this code will never come while you use this programm right :)
}
}
// Example of using somewhere in your program:
static void Main(string[] args)
{
List<Item> items = new List<Item>();
items.Add(new Item() { name = "Anna", chance = 100});
items.Add(new Item() { name = "Alex", chance = 125});
items.Add(new Item() { name = "Dog", chance = 50});
items.Add(new Item() { name = "Cat", chance = 35});
Item newItem = ProportionalWheelSelection.SelectItem(items);
}