Last active
January 2, 2020 22:09
-
-
Save ZacharyPatten/728658c5bc13634ee10cdaf3d6ac7baa to your computer and use it in GitHub Desktop.
An example of weighted random generation.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
namespace MathSyntax | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
const int iterations = 10000000; | |
Random random = new Random(); | |
IEnumerable<(int, double)> pool = Enumerable.Range(0, 10).Select(i => (i, (double)i)); | |
int[] occurences = new int[pool.Count()]; | |
for (int i = 0; i < iterations; i++) | |
occurences[random.Next(pool)]++; | |
double totalWeight = pool.Select(x => x.Item2).Sum(); | |
double[] expectedProbability = new double[pool.Count()]; | |
for (int i = 0; i < expectedProbability.Length; i++) | |
expectedProbability[i] = (double)i / totalWeight; | |
for (int i = 0; i < expectedProbability.Length; i++) | |
Console.WriteLine("Value: " + i + " Expected: " + expectedProbability[i] + " Actual: " + ((double)occurences[i] / (double)iterations)); | |
} | |
} | |
public static class RandomExtensions | |
{ | |
public static T Next<T>(this Random random, IEnumerable<(T Value, double Weight)> pool) | |
{ | |
double totalWeight = 0; | |
foreach (var possibility in pool) | |
{ | |
if (possibility.Weight < 0) | |
throw new ArgumentOutOfRangeException("A value in the pool had a weight less than zero."); | |
totalWeight += possibility.Weight; | |
} | |
if (totalWeight == 0) | |
throw new ArgumentOutOfRangeException("The total weight of all values in the pool was zero."); | |
if (double.IsInfinity(totalWeight)) | |
throw new ArgumentOutOfRangeException("The total weight of all values in the pool was an infinite double."); | |
double randomDouble = random.NextDouble(); | |
double range = 0; | |
foreach (var possibility in pool) | |
{ | |
range += possibility.Weight; | |
if (randomDouble < range / totalWeight) | |
return possibility.Value; | |
} | |
throw new Exception("There is a bug in the code."); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment