Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save develohpanda/87b8e0382205fb37d133bf13e12d1e74 to your computer and use it in GitHub Desktop.
Save develohpanda/87b8e0382205fb37d133bf13e12d1e74 to your computer and use it in GitHub Desktop.
Weighted Random Selection With Limited Allocations - a modified implementation of the solution found at http://programmers.stackexchange.com/a/150642/244423
/// <summary>
/// Selects a random element from input list using the allocations remaining to sway selection
/// T must have AllocationRemaining, Weight and Id properties on it.
/// </summary>
public T SelectRandom<T>(List<T> objects)
{
int totalWeight = 0;
T selected = default(T);
foreach (T obj in objects)
{
int weight = data.AllocationsRemaining;
if (weight == 0) continue;
int r = new Random().Next(totalWeight + weight);
if (r >= totalWeight)
selected = data;
totalWeight += weight;
}
if (selected == default(T))
return objects.Where(t => t.Weight > 0).RandomElement();
objects.First(t => t.Id == selected.Id).AllocationsRemaining--;
return selected;
}
/// <summary>
/// Allocating depending on weights, for the method above
/// </summary>
public void Allocate<T>(List<t> objects, int totalAllocations)
{
double totalSegments = objects.Sum(t => t.Weight);
double allocationsPerSegment = totalAllocations / totalSegments;
foreach (T obj in objects)
{
obj.AllocationsRemaining = Convert.ToInt16(Math.Round(obg.Weight * allocationsPerSegment, MidpointRounding.AwayFromZero));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment