# 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.

## 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 on other sites
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 percentageSum = 0;for(i = 0; i < Table.Size; ++i){    if(Sum  + Table.Frequency >= Percentage)         return Table.Letter;    Sum += Table.Frequency; }

##### 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.)

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633708
• Total Posts
3013475
×