Loading ...
Sorry, an error occurred while loading the content.

5186Re: [hackers-il] Algorithm for randomly choosing a question

Expand Messages
  • Ori Idan
    Jul 6, 2012


      I want the application to be able to select any question randomly, but
      with different weights, so that:
      - A question the user never saw has weight of (say) 0.5.
      - A question the user answered wrongly has weight of 1 (i.e. such a
      question is twice more likely to be presented than a question never
      seen).
      - A question the user answered correctly has weight of 0.005 (i.e. it is
      100 times less likely to be seen again than a question never seen
      before).

      A brute force approach is as follows (actual probabilities may differ
      from the given weights, due to the finite probability of choosing the
      same i again; I am ignoring this complication for now).

      1. Select a number randomly from range [1,N], call it i.
      2. If the user answered question i wrongly, it is chosen.
      3. If the user never saw question i, select randomly real x from range
      [0,1].
      If x <= 0.5, i is chosen.
      Otherwise, go to 1.
      4. If the user already answered question i correctly, select randomly
      real x from range [0,1].
      If x <= 0.005, i is chosen.
      Otherwise, go to 1.

      My wish is to have an algorithm which requires only bounded number of
      computations of random numbers (i.e. no loop) to accomplish the above.
      Assume that N is large, so keeping lists of questions in memory is ruled
      out.

      You don't have to keep a list of questions, just a list of numbers where each number represent a question.
      A question you want to appear twice as much as any other, put it twice in the list.
      For a question you want to appear 100 times less then any other, use the algorithm you suggested.

      -- 
      Ori Idan

    • Show all 7 messages in this topic