Jump to content
  • Advertisement
Sign in to follow this  
darkpegasus

Algorithm question: getting a weighted value

This topic is 3693 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a table that tells me the frequency of each letter in the English language. For example "A" appears 8.167% of the time. How would I generate a random letter based on this frequency?

Share this post


Link to post
Share on other sites
Advertisement
The most straight forward way I can think of it to generate a random floating point number greater than zero and less than or equal to 100, and then iterate forward through your table, adding each letters frequency to a sort of frequency sum. When that sum is greater than or equal to your random percentage value, break out and use the value you got up to in your table.

Like this:



Percentage = Random percentage
Sum = 0;

for(i = 0; i < Table.Size; ++i)
{

if(Sum + Table.Frequency >= Percentage)
return Table.Letter;

Sum += Table.Frequency;
}


Share this post


Link to post
Share on other sites
First, convert your probability distribution function to a cumulative distribution function. In C++, you can use the standard library algorithm std::partial_sum() for this.

Then, pick a random number out of the maximum range (last element in the CDF - this way, you don't need to normalize). Select the first index where the CDF is greater than the random number. In C++, you can do this with the standard library algorithm std::upper_bound().

(Edited with a correction and links.)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!