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

5185Algorithm for randomly choosing a question

Expand Messages
  • Omer Zak
    Jul 6, 2012
    • 0 Attachment
      I am developing an Android application which is intended to help people
      prepare for the theory test for driving license.

      Basically, there is a database of N questions, numbered from 1 until N
      without gaps.
      Each time the application chooses randomly a question and the user
      answers it.
      The application records whether the answer was correct or not and then
      selects the next question for display.

      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.

      Any suggestions?

      --- Omer


      --
      Did you shave a yak today?
      My own blog is at http://www.zak.co.il/tddpirate/

      My opinions, as expressed in this E-mail message, are mine alone.
      They do not represent the official policy of any organization with which
      I may be affiliated in any way.
      WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
    • Show all 7 messages in this topic