Weighted random letter in Objective-C
objective-c, random
Solution
Not sure if this would work, but it seems like it might do the trick:
- Take your list of letters and frequencies and sort them from smallest frequency to largest.
- Create a 26 element array where each element n contains the sum of all previous weights and the element n from the list of frequencies. Make note of the sum in the last element of the array
- Generate a random number between 0 and the sum you made note of above
- Do a binary search of the array of sums until you reach the element where that number would fall
That's a little hard to follow, so it would be something like this:
- if you have a 5 letter alphabet with these frequencies, a = 5%, b = 20%, c = 10%, d = 40%, e = 25%, sort them by frequency: a,c,b,e,d
- Keep a running sum of the elements: 5, 15, 35, 60, 100
- Generate a random number between 0 and 100. Say it came out 22.
- Do a binary search for the element where 22 would fall. In this case it would be between element 2 and 3, which would be the letter "b" (rounding up is what you want here, I think)
Problem
I need a simple way to randomly select a letter from the alphabet, weighted on the percentage I want it to come up. For example, I want the letter 'E' to come up in the random function 5.9% of the time, but I only want 'Z' to come up 0.3% of the time (and so on, based on the average occurrence of each letter in the alphabet). Any suggestions? The only way I see is to populate an array with, say, 10000 letters (590 'E's, 3 'Z's, and so on) and then randomly select an letter from that array, but it seems memory intensive and clumsy.