Efficient algorithm to randomly select items with frequency

Answer 1

This sounds like roulette wheel selection, mainly used for the selection process in genetic/evolutionary algorithms.

Look at http://stackoverflow.com/questions/177271/roulette-selection-in-genetic-algorithms

Answer 2

You could create the target array, then loop through the words determining the probability that it should be picked, and replace the words in the array according to a random number.

For the first word the probability would be f₀/m₀ (where m_n=f₀+..+f_n), i.e. 100%, so all positions in the target array would be filled with w₀.

For the following words the probability falls, and when you reach the last word the target array is filled with randomly picked words accoding to the frequency.

Example code in C#:

public class WordFrequency {

 public string Word { get; private set; }
 public int Frequency { get; private set; }

 public WordFrequency(string word, int frequency) {
  Word = word;
  Frequency = frequency;
 }

}

WordFrequency[] words = new WordFrequency[] {
 new WordFrequency("Hero", 80),
 new WordFrequency("Monkey", 4),
 new WordFrequency("Shoe", 13),
 new WordFrequency("Highway", 3),
};

int p = 7;
string[] result = new string[p];
int sum = 0;
Random rnd = new Random();
foreach (WordFrequency wf in words) {
 sum += wf.Frequency;
 for (int i = 0; i < p; i++) {
  if (rnd.Next(sum) < wf.Frequency) {
   result[i] = wf.Word;
  }
 }
}