5185Algorithm for randomly choosing a question
- Jul 6, 2012I 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
Each time the application chooses randomly a question and the user
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
- 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
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
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
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
- Next post in topic >>