repetir - propiedad random c#

Generador de números aleatorios de probabilidad distribuida

Question

Quiero generar un número basado en una probabilidad distribuida. Por ejemplo, digamos que hay las siguientes ocurrencias de cada número:

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    

¿Cómo hago un generador de números aleatorios que devuelva números basados ​​en esta distribución de probabilidad?

Estoy feliz de que esto se base en un conjunto estático y codificado por ahora, pero eventualmente quiero que derive la distribución de probabilidad de una consulta de base de datos.

He visto ejemplos similares como este, pero no son muy genéricos. ¿Alguna sugerencia?

Answer 1

Aquí hay una implementación usando la función de distribución inversa :

using System;
using System.Linq;

    // ...
    private static readonly Random RandomGenerator = new Random();

    private int GetDistributedRandomNumber()
    {
        double totalCount = 208;

        var number1Prob = 150 / totalCount;
        var number2Prob = (150 + 40) / totalCount;
        var number3Prob = (150 + 40 + 15) / totalCount;

        var randomNumber = RandomGenerator.NextDouble();

        int selectedNumber;

        if (randomNumber < number1Prob)
        {
            selectedNumber = 1;
        }
        else if (randomNumber >= number1Prob && randomNumber < number2Prob)
        {
            selectedNumber = 2;
        }
        else if (randomNumber >= number2Prob && randomNumber < number3Prob)
        {
            selectedNumber = 3;
        }
        else
        {
            selectedNumber = 4;
        }

        return selectedNumber;
    }

Un ejemplo para verificar la distribución aleatoria:

        int totalNumber1Count = 0;
        int totalNumber2Count = 0;
        int totalNumber3Count = 0;
        int totalNumber4Count = 0;

        int testTotalCount = 100;

        foreach (var unused in Enumerable.Range(1, testTotalCount))
        {
            int selectedNumber = GetDistributedRandomNumber();

            Console.WriteLine($"selected number is {selectedNumber}");

            if (selectedNumber == 1)
            {
                totalNumber1Count += 1;
            }

            if (selectedNumber == 2)
            {
                totalNumber2Count += 1;
            }

            if (selectedNumber == 3)
            {
                totalNumber3Count += 1;
            }

            if (selectedNumber == 4)
            {
                totalNumber4Count += 1;
            }
        }

        Console.WriteLine("");
        Console.WriteLine($"number 1 -> total selected count is {totalNumber1Count} ({100 * (totalNumber1Count / (double) testTotalCount):0.0} %) ");
        Console.WriteLine($"number 2 -> total selected count is {totalNumber2Count} ({100 * (totalNumber2Count / (double) testTotalCount):0.0} %) ");
        Console.WriteLine($"number 3 -> total selected count is {totalNumber3Count} ({100 * (totalNumber3Count / (double) testTotalCount):0.0} %) ");
        Console.WriteLine($"number 4 -> total selected count is {totalNumber4Count} ({100 * (totalNumber4Count / (double) testTotalCount):0.0} %) ");

Ejemplo de salida:

selected number is 1
selected number is 1
selected number is 1
selected number is 1
selected number is 2
selected number is 1
...
selected number is 2
selected number is 3
selected number is 1
selected number is 1
selected number is 1
selected number is 1
selected number is 1

number 1 -> total selected count is 71 (71.0 %) 
number 2 -> total selected count is 20 (20.0 %) 
number 3 -> total selected count is 8 (8.0 %) 
number 4 -> total selected count is 1 (1.0 %)

Answer 2

El enfoque general es incluir números aleatorios distribuidos uniformemente desde el intervalo 0..1 en el inverso de la función de distribución acumulativa de su distribución deseada.

Por lo tanto, en su caso, solo dibuje un número aleatorio x de 0..1 (por ejemplo, con Random.NextDouble() ) y basado en su valor de retorno

• 1 si 0 <= x <150/208,
• 2 si 150/208 <= x <190/208,
• 3 si 190/208 <= x <205/208 y
• 4 de lo contrario.

Answer 3

Gracias por todas sus soluciones chicos! ¡Muy apreciado!

@Menjaraz Intenté implementar su solución ya que parece muy amigable con los recursos, sin embargo, tuve algunas dificultades con la sintaxis.

Por ahora, acabo de transformar mi resumen en una lista plana de valores utilizando LINQ SelectMany () y 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));
    }
}

Answer 4

Haga esto solo una vez:

• Escriba una función que calcule una matriz cdf dada una matriz pdf. En su ejemplo, la matriz pdf es [150,40,15,3], la matriz cdf será [150,190,205,208].

Haga esto cada vez:

• Obtenga un número aleatorio en [0,1), multiplíquelo por 208, trunque hacia arriba (o hacia abajo: le dejo a usted que piense en los casos de esquina) Tendrá un número entero en 1..208. Nómbrelo r.
• Realizar una búsqueda binaria en la matriz de cdf para r. Devuelve el índice de la celda que contiene r.

El tiempo de ejecución será proporcional al registro del tamaño de la matriz de pdf dada. Lo que es bueno. Sin embargo, si el tamaño de su matriz siempre será tan pequeño (4 en su ejemplo), realizar una búsqueda lineal es más fácil y también tendrá un mejor rendimiento.

Answer 5

Sé que este es un post antiguo, pero también busqué un generador de este tipo y no estaba satisfecho con las soluciones que encontré. Así que escribí el mío y quiero compartirlo con el mundo.

Simplemente llame "Agregar (...)" algunas veces antes de llamar "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
    }
}

Answer 6

Usa mi método. Es simple y fácil de entender. No cuento la porción en el rango 0 ... 1, solo uso "Probabilityp Pool" (suena bien, ¿no?)

En el diagrama circular puedes ver el peso de cada elemento en la piscina.

Aquí puede ver una implementación de probabilidad acumulativa para la ruleta.

`

// 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);
        }

Answer 7

Esta pregunta explica los diversos enfoques para generar números aleatorios con diferentes probabilidades. Según este artículo , que se muestra en esa pregunta, el mejor enfoque de este tipo (en términos de complejidad de tiempo) es el llamado "método de alias" de Michael Vose.

Para su comodidad, he escrito y proporciono aquí una implementación en C # de un generador de números aleatorios que implementa el método de alias:

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''s 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];
    }
}

Ejemplo:

 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

Pongo este código en el dominio público.