Simple collection that returns a random object based on a probability(weight)
Add an object using the Add() function and use the Next() function to return a random object:
Here is a download link from Microsoft SkyDrive:
Random by probability/weight
public class RandomByProbabilityCollection<T>
{
/// <summary>
/// The object you are pooling.
/// </summary>
private List<T> options;
/// <summary>
/// The inverse of the probability that object will be selected.
/// </summary>
private List<byte> probability;
/// <summary>
/// Inverse probability that the items had last SelectNext call.
/// </summary>
private List<byte> lastCallProbability;
/// <summary>
/// Currently selectable objects.
/// </summary>
private List<int> currentList;
/// <summary>
/// Objects that can't be selected now.
/// </summary>
private List<int> candidateList;
/// <summary>
/// Rendom number generator.
/// </summary>
private Random randomGenerator;
/// <summary>
/// Generate a new collection of items that can be selected based on a probability.
/// </summary>
/// <param name="initialSize">The initial size of the collection.</param>
/// <param name="maxProbability">The maximum priority for an item.</param>
/// <param name="maxExtraIterations">Extra iteration to try and load more then 2 items.</param>
public RandomByProbabilityCollection(int initialSize, byte maxProbability, int maxExtraIterations)
{
probability = new List<byte>(initialSize);
lastCallProbability = new List<byte>(initialSize);
options = new List<T>(initialSize);
currentList = new List<int>(initialSize);
candidateList = new List<int>(initialSize);
randomGenerator = new Random();
this.max2Iteration = maxExtraIterations;
this.maxProbability = maxProbability;
}
//Disabled items iteration step.
private byte min = 1;
//The maximum available priority.
private readonly byte maxProbability = 75;
//Maximum number of iteration used to discover atleast 2 comparable objects.
private readonly int max2Iteration = 10;
//Set the items iteration step.
private void SetMin(byte current)
{
if (current < min && current > 0)
{
min = current;
}
}
//Calculate the priority for a given item.
private byte CalculatePriority(int probability)
{
int p = (probability > maxProbability ? maxProbability : probability);
p = (maxProbability - p);
return (byte)p;
}
/// <summary>
/// Add an item to the collection.
/// </summary>
/// <param name="probability">The probability that this item will be selected 0 to 75.</param>
/// <param name="obj">The object.</param>
public void Add(byte probability, T obj)
{
byte p2 = CalculatePriority(probability);
SetMin(p2);
this.probability.Add(p2);
this.lastCallProbability.Add(p2);
this.candidateList.Add(this.probability.Count - 1);
this.options.Add(obj);
}
//Check if there are any objects available for selection.
private void CheckPosibility()
{
if (candidateList.Count > 0)
{
for (int i = 0; i < candidateList.Count; i++)
{
int theIndex = candidateList[i];
if (probability[theIndex] == maxProbability)
{
continue;
}
int lastProbability = lastCallProbability[theIndex];
if (lastProbability < 1)
{
lastCallProbability[theIndex] = probability[theIndex];
candidateList.RemoveAt(i);
currentList.Add(theIndex);
i--;
}
else
{
if (lastCallProbability[theIndex] < min)
{
lastCallProbability[theIndex] = min;
continue;
}
lastCallProbability[theIndex] -= min;
}
}
}
}
/// <summary>
/// Select a random object from the collection based on it's probability.
/// </summary>
/// <returns></returns>
public T Next()
{
if (options.Count < 1)
{
//throw new Exception("The collection is empty but you are trying to ge a value");
return default(T);
}
if (options.Count == 1)
{
return options[0];
}
int skipCount = max2Iteration;
while (currentList.Count < 2 && skipCount > 0)
{
skipCount--;
CheckPosibility();
}
int overflowTest = 0;
while (currentList.Count < 1)
{
overflowTest++;
CheckPosibility();
if (overflowTest > 100)
{
for (int i = 0; i < probability.Count; i++)
{
if (probability[i] != maxProbability)
{
overflowTest = 0;
break;
}
}
if (overflowTest != 0)
{
throw new Exception("All objects have a priority of 0, this function will never return");
}
}
}
int option = randomGenerator.Next(0, currentList.Count);
int selectedIndex = currentList[option];
candidateList.Add(selectedIndex);
currentList.RemoveAt(option);
return options[selectedIndex];
}
/// <summary>
/// Remove an item from the collection based on it's index in the collection.
/// </summary>
/// <param name="index">The index of the item to remove.</param>
/// <returns>True if an item was removed.</returns>
public bool RemoveAt(int index)
{
if (options.Count > index)
{
int maxProbability = probability[index];
this.probability.RemoveAt(index);
int currentLastCallProbability = lastCallProbability[index];
this.lastCallProbability.RemoveAt(index);
if (currentLastCallProbability >= maxProbability)
{
this.currentList.Remove(index);
}
else
{
this.candidateList.Remove(index);
}
this.options.RemoveAt(index);
for (int i = 0; i < currentList.Count; i++)
{
if (currentList[i] > index)
{
currentList[i]--;
}
}
for (int i = 0; i < candidateList.Count; i++)
{
if (candidateList[i] > index)
{
candidateList[i]--;
}
}
return true;
}
else
{
return false;
}
}
/// <summary>
/// Remove an item from the collection.
/// </summary>
/// <param name="obj">The item to remove.</param>
/// <returns>True if an item was removed.</returns>
public bool Remove(T obj)
{
int indexOfT = options.IndexOf(obj);
return RemoveAt(indexOfT);
}
/// <summary>
/// Clear the collection.
/// </summary>
public void Clear()
{
this.probability.Clear();
this.lastCallProbability.Clear();
this.currentList.Clear();
this.candidateList.Clear();
this.options.Clear();
}
/// <summary>
/// Sets the capacity to the actual number of elements in the list,
/// if that number is less than a threshold value.
/// </summary>
public void TrimExcess()
{
options.TrimExcess();
probability.TrimExcess();
lastCallProbability.TrimExcess();
}
/// <summary>
/// Change priority on a item at a given index.
/// </summary>
/// <param name="index">The index of the item that you want to change probability for.</param>
/// <param name="probability">The new probability.</param>
/// <returns>True if changed.</returns>
public bool ChangeProbabilityAt(int index, byte probability)
{
if (options.Count > index)
{
this.probability[index] = CalculatePriority(probability);
if (this.currentList.Contains(index))
{
this.currentList.Remove(index);
this.candidateList.Add(index);
}
return true;
}
return false;
}
/// <summary>
/// Change priority on a item.
/// </summary>
/// <param name="index">The item that you want to change probability for.</param>
/// <param name="probability">The new probability.</param>
/// <returns>True if changed.</returns>
public bool ChangeProbability(T obj, byte probability)
{
int indexOfT = options.IndexOf(obj);
return ChangeProbabilityAt(indexOfT, probability);
}
/// <summary>
/// Number of items in the collection.
/// </summary>
public int Count
{
get
{
return options.Count;
}
}
/// <summary>
/// Indexed return.
/// </summary>
/// <param name="index">The index of the object.</param>
/// <returns>The object.</returns>
public T this[int index]
{
get
{
return options[index];
}
}
}
