0 Replies - 1409 Views - Last Post: 17 April 2012 - 09:22 AM

#1 anonymouscodder  Icon User is offline

  • member icon

Reputation: 126
  • View blog
  • Posts: 710
  • Joined: 01-January 10

Weighted Random

Posted 17 April 2012 - 09:22 AM

Description: A random that supports selecting n number of elements considering each element weight.

/// <summary>
/// Randomly selects the specified quantity of elements from the passed elements considering it element weight.
/// </summary>
/// <param name="elements">Elements to chose from, the key is the element itself and the value the element weight</param>
/// <param name="count">Quantity to be selected</param>
/// <returns>Selected elements</returns>
public static object[] WeightedRandom(KeyValuePair<object, int>[] elements, int count)
{
	if(count >= elements.Length)
	{
		throw new ArgumentException("the quantity to select must be higher than the quantity of elements to select from");
	}

	//Chosen elements (the index in elements array)
	int[] chosen = new int[count];

	//Iterating array of elements to be chosen
	for (int i = 0; i < chosen.Length; ++i)
	{
		//Total weight for this iteration
		int totalWeight = 0;

		//Total iteration weight in ranges
		KeyValuePair<int, int>[] ranges = new KeyValuePair<int, int>[elements.Length - i];

		//Iterating elements, adds the corresponding range from each non selected element to the ranges array
		for (int j = 0, k = 0; j < elements.Length; ++j)
		{
			#region to not include already selected elements
			bool contains = false;
			for (int l = 0; l < i; ++l)
			{
				if (j == chosen[l])
				{
					contains = true;
					break;
				}
			}
			if (contains)
			{
				continue;
			}
			#endregion

			totalWeight += elements[j].Value;
			ranges[k++] = new KeyValuePair<int, int>(j, totalWeight);
		}

		//Randomizes a value in the total weight
		int random = new Random().Next(totalWeight + 1);

		//Find out what item was chosen (checks in which range the randomized number is and the range represents an element in the passed elements)
		for (int j = 0; j < ranges.Length; ++j)
		{
			if (j == 0)
			{
				if (random <= ranges[j].Value)
				{
					chosen[i] = ranges[j].Key;
					break;
				}
			}
			else if (random > ranges[j - 1].Value && random <= ranges[j].Value)
			{
				chosen[i] = ranges[j].Key;
				break;
			}
		}
	}

	//Building up array with selected values to return
	object[] selected = new object[chosen.Length];
	for (int i = 0; i < selected.Length; ++i)
	{
		selected[i] = elements[chosen[i]].Key;
	}

	return selected;
}
//developed @ sydle


Is This A Good Question/Topic? 0
  • +

Page 1 of 1