Weighted random

I don't know enough about C# to know what to try. It's been a long day of coding!

Goal: I am building a game where genes are simulated. Some genes are rarer than others (1% or less), so i made different dictionaries with the chances of getting different genes. I want to make a function that generates a number from 1-100 (this part is done), then returns the corresponding gene from the dictionary. I want to be able to make many dictionaries but use the same function to handle them all.

Code so far:

Code (CSharp):

1.  
2.     System.Random rnd = new System.Random();
3.     //one gene
4.     Dictionary<string, int> extGenes = new Dictionary<string, int>()
5.     {
6.       {"AA", 10},
7.       {"Aa", 20},
8.       {"aA", 20},
9.       {"aa", 50}
10.     };
11.  
12.     private void WeightedRandom()
13.     {
14.         int probability = rnd.Next(1, 100);
15.         //maybe if i redo the dictionary to show a range instead of a probability? so {"AA", 1.10},
16.         //some kind of loop?
17.     }

I would really appreciate any tips! I have this working in pho but just learning C#

 

Use a list, instead of a dictionary. Then iterate through your list. If p (your random number) is <= the probability on your current item, return that item. Otherwise, reduce p by the probability of the current item, and go on to the next one.

If your items add up to a total probability of 100, then this is guaranteed to pick one. And it will pick from them in proportion to their probability.

 

How do I know what item to return if I use a list? shouldn't there be a key to go with the value? This is what i have so far, but this will return two genes if the probability is high enough:

Dictionary<string, string> extGenes = new Dictionary<string, string>()
{
{"AA", "10"}, {"Aa", "30"}, {"aA", "50"}, {"aa", "100"}
};
private void WeightedRandom(Dictionary<string, string> dict)
{
int probability = rnd.Next(1, 100);
Debug.Log($"probability: " + probability);
foreach (var item in dict)
{
if (probability <= int.Parse(item.Value))
{
Debug.Log(item.Key);
}
}
}

 

Ah, you would either use a list of structs (each containing the key along with the value), or two lists you keep in parallel (one for keys, the other for values).

And actually, your approach will work — it's just not as efficient as either of the options above. But your loop should look like this:

Code (csharp):

1. int p = rnd.Next(0, 100);  // using p because it's not really "probability" but "remaining probability"
2. foreach (var item in dict) {
3.     if (p < int.Parse(item.Value)) {  // ...uh... why aren't you storing your probabilities as int instead of string?!
4.       return item.Key
5.     }
6.     p -= int.Parse(item.Value);   // <----- HERE'S THE KEY BIT
7. }

 

Here is the original code i had working in php, maybe it will help? I obviously didn't write this, or i would understand fully how it works. Maybe the "=>" in the array is what is closing the upper bounds of the range?

Code (CSharp):

1. function weightedRandom(array $weightedValues) {
2.     $rand = mt_rand(1, (int) array_sum($weightedValues));
3.  
4.     foreach ($weightedValues as $key => $value) {
5.       $rand -= $value;
6.       if ($rand <= 0) {
7.         return $key;
8.       }}}
9.  
10. $greAlleles = array('g' => 95, 'G' => 5);
11. $greGenes = weightedRandom($greAlleles).''.weightedRandom($greAlleles);
12. $gre = $greGenes;

 

Ok I got it! Now it works with different numbers of alleles too, so it scales with really complicated sets of genes. Thanks for the help!

Code (CSharp):

1. Dictionary<string, int> extGenes = new Dictionary<string, int>()
2.     {
3.       //{"A", 60}, {"B", 35}, {"C", 15}
4.       {"a", 50}, {"A", 50}
5.     };
6.  
7.     private void WeightedRandom(Dictionary<string, int> dict)
8.     {
9.         int p = rnd.Next(1, 100);
10.         string givenAllele = "0";
11.         foreach (var item in dict)
12.         {
13.             if (p <= item.Value & p > 0)
14.             {
15.                 givenAllele = item.Key;
16.             }
17.                 p -= item.Value;
18.         }
19.     }