Choose items based on popularity: Avoid the glorified look

Question

I have a website where users can post and vote on offers. On the first page, I initially list 10 sentences, and the title selects a new random sentence every 7 seconds.

I want the votes to influence the likelihood of a sentence appearing, both in a list of 10 sentences and in a sentence of a headline. For this, I have a small algorithm for calculating popularity, taking into account voices, age and a couple of other things (many settings are required).

In any case, after starting the algorithm, I have a dictionary of sentences and popularity index, sorted by popularity:

{ S = Suggestion1, P = 0.86 } { S = Suggestion2, P = 0.643 } { S = Suggestion3, P = 0.134 } { S = Suggestion4, P = 0.07 } { S = Suggestion5, P = 0.0 } { . . .} 

I do not want this to be an illustrious view, so I would like to introduce some random element into the selection process.

In short, I would like popularity to be the probability that an offer is selected from a list .

With a complete list of offers / popularity, how do I go for a choice of 10 based on probabilities? How can I apply the same to the loop header clause?

Answer 1

I'm afraid I don’t know how to do this very quickly, but if you have a collection in mind, you can do it like this:

Please note that you do not need to sort the list for this algorithm to work.

• First sum up all the probabilities (if the probability is related to popularity, just sum the popularity numbers, where I assume that higher values ​​mean a higher probability)
• Calculate a random number between 0 and but not including this amount
• Start at one end of the list and go through it.
• For each item, if the random number you received is less than popularity, select this item.
• If not, subtract the item popularity from the random number and continue to the next

If the list is static, you can create ranges and execute binary queries, but if the list keeps changing, I don't know a better way.

Here is an example LINQPad that demonstrates:

 void Main() { var list = Enumerable.Range(1, 9) .Select(i => new { V = i, P = i }) .ToArray(); list.Dump("list"); var sum = (from element in list select element.P).Sum(); Dictionary<int, int> selected = new Dictionary<int, int>(); foreach (var value in Enumerable.Range(0, sum)) { var temp = value; var v = 0; foreach (var element in list) { if (temp < element.P) { v = element.V; break; } temp -= element.P; } Debug.Assert(v > 0); if (!selected.ContainsKey(v)) selected[v] = 1; else selected[v] += 1; } selected.Dump("how many times was each value selected?"); } 

Output:

  list 
 [] (9 items)  
  VP
  eleven 
  2 2 
  3 3 
  4 4 
  5 5 
  6 6 
  7 7 
  8 8 
  9 9 
 45 45 <- sum

 how many times was each value selected? 
 Dictionary <Int32, Int32> (9 items)  
 Key value
  eleven 
  2 2 
  3 3 
  4 4 
  5 5 
  6 6 
  7 7 
  8 8 
  9 9 
      45 <- again, sum