Verteilte Wahrscheinlichkeit random number generator

Diese Frage erläutert die verschiedenen Ansätze für die Generierung von Zufallszahlen mit verschiedenen Wahrscheinlichkeiten. Nach dieser Artikelgezeigt, auf, die Frage, die am besten so Vorgehen (in Bezug auf die Zeit-Komplexität) ist die so genannte "alias-Methode" von Michael Vose.

Für Ihre Bequemlichkeit, habe ich geschrieben und bieten hier eine C# - Implementierung eines Zufallszahlengenerators Umsetzung der alias Methode:

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

Beispiel:

 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

Stelle ich diesen code in der public domain.

InformationsquelleAutor der Antwort Peter O.

Ich weiß, dies ist eine alte post, aber ich habe auch gesucht wie ein generator und war nicht zufrieden mit den Lösungen, die ich gefunden. Also schrieb ich mein eigenes wollen und teilen Sie es der Welt.

Rufen Sie einfach "Hinzufügen(...)" einige Male, bevor Sie anrufen "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
    }
}

InformationsquelleAutor der Antwort Kithoras Carzyl

Verwendung meiner Methode. Es ist einfach und leicht zu verstehen.
Ich zähle nicht Teil im Bereich 0...1, ich habe gerade mit "Probabilityp Pool" (klingt cool, ja?)

Bei Kreis-Diagramm können Sie sehen, das Gewicht jedes Elements in pool

Hier sehen Sie eine Umsetzung der kumulierte Wahrscheinlichkeit für roulette

`

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

InformationsquelleAutor der Antwort Alexandr Martysh