Algorithm for randomly choosing a question
Omer Zak <w1-W6cp89mEpD1mR6Xm/[email protected]> Sat, 07 Jul 2012 07:53:31 +0300
| Newsgroups | gmane.culture.hackers.israel |
|---|---|
| Message-ID | <1341636811.13711.21.camel@c4> |
--PKBLb89OSKu99VKAhZpT1ABdnNUiOWnegOUfZLD
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
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
--PKBLb89OSKu99VKAhZpT1ABdnNUiOWnegOUfZLD
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 7bit
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
</head>
<body style="background-color: #fff;">
<span style="display:none"> </span>
<!--~-|**|PrettyHtmlStartT|**|-~-->
<div id="ygrp-mlmsg" style="position:relative;">
<div id="ygrp-msg" style="z-index: 1;">
<!--~-|**|PrettyHtmlEndT|**|-~-->
<div id="ygrp-text" >
<p>I am developing an Android application which is intended to help people<br>
prepare for the theory test for driving license.<br>
<br>
Basically, there is a database of N questions, numbered from 1 until N<br>
without gaps.<br>
Each time the application chooses randomly a question and the user<br>
answers it.<br>
The application records whether the answer was correct or not and then<br>
selects the next question for display.<br>
<br>
I want the application to be able to select any question randomly, but<br>
with different weights, so that:<br>
- A question the user never saw has weight of (say) 0.5.<br>
- A question the user answered wrongly has weight of 1 (i.e. such a<br>
question is twice more likely to be presented than a question never<br>
seen).<br>
- A question the user answered correctly has weight of 0.005 (i.e. it is<br>
100 times less likely to be seen again than a question never seen<br>
before).<br>
<br>
A brute force approach is as follows (actual probabilities may differ<br>
from the given weights, due to the finite probability of choosing the<br>
same i again; I am ignoring this complication for now).<br>
<br>
1. Select a number randomly from range [1,N], call it i.<br>
2. If the user answered question i wrongly, it is chosen.<br>
3. If the user never saw question i, select randomly real x from range<br>
[0,1].<br>
If x <= 0.5, i is chosen.<br>
Otherwise, go to 1.<br>
4. If the user already answered question i correctly, select randomly<br>
real x from range [0,1].<br>
If x <= 0.005, i is chosen.<br>
Otherwise, go to 1.<br>
<br>
My wish is to have an algorithm which requires only bounded number of<br>
computations of random numbers (i.e. no loop) to accomplish the above.<br>
Assume that N is large, so keeping lists of questions in memory is ruled<br>
out.<br>
<br>
Any suggestions?<br>
<br>
--- Omer<br>
<br>
-- <br>
Did you shave a yak today?<br>
My own blog is at <a href="http://www.zak.co.il/tddpirate/">http://www.zak.co.il/tddpirate/</a><br>
<br>
My opinions, as expressed in this E-mail message, are mine alone.<br>
They do not represent the official policy of any organization with which<br>
I may be affiliated in any way.<br>
WARNING TO SPAMMERS: at <a href="http://www.zak.co.il/spamwarning.html">http://www.zak.co.il/spamwarning.html</a><br>
<br>
</p>
</div>
<!--~-|**|PrettyHtmlStart|**|-~-->
<div style="color: #fff; height: 0;">__._,_.___</div>
<div id="ygrp-actbar" style="clear: both; margin-bottom: 10px; white-space: nowrap; color: #666; padding-top: 15px;">
<div>
<a href="mailto:w1-W6cp89mEpD1mR6Xm/[email protected]?subject=Re%3A%20Algorithm%20for%20randomly%20choosing%20a%20question" style="margin-right: 0; padding-right: 0;">
Reply to <span style="font-weight: 700;">sender</span></a> |
<a href="mailto:[email protected]?subject=Re%3A%20Algorithm%20for%20randomly%20choosing%20a%20question">
Reply to <span style="font-weight: 700;">group</span></a> |
<a href="http://groups.yahoo.com/group/hackers-il/post;_ylc=X3oDMTJwYWxnNDk4BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzUxODUEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzQxNjM2Nzg0?act=reply&messageNum=5185">Reply <span style="font-weight: 700;">via web post</span></a> |
<a href="http://groups.yahoo.com/group/hackers-il/post;_ylc=X3oDMTJlbmE0MDlyBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTM0MTYzNjc4NA--" style="font-weight: 700;">Start a New Topic</a>
</div>
<a href="http://groups.yahoo.com/group/hackers-il/message/5185;_ylc=X3oDMTM0dDBqNm1pBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzUxODUEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQMxMzQxNjM2Nzg0BHRwY0lkAzUxODU-">Messages in this topic</a>
(<span style="font-weight: 700;">1</span>)
</div>
<!------- Start Nav Bar ------>
<!-- |**|begin egp html banner|**| -->
<div id="ygrp-vital" style="background-color: #e0ecee; font-family: Verdana; font-size: 10px; margin-bottom: 10px; padding: 10px;">
<span id="vithd" style="font-weight: bold; color: #333; text-transform: uppercase; ">Recent Activity:</span>
<ul style="list-style-type: none; margin: 0; padding: 0; display: inline;">
<li style="border-right: 1px solid #000; font-weight: 700; display: inline; padding: 0 5px; margin-left: 0;">
<span class="cat"><a href="http://groups.yahoo.com/group/hackers-il/members;_ylc=X3oDMTJmcnM0ZmoyBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZtYnJzBHN0aW1lAzEzNDE2MzY3ODQ-?o=6" style="text-decoration: none;">New Members</a></span>
<span class="ct" style="color: #ff7900;">1</span>
</li>
</ul>
<div style="clear: both; padding-top: 2px; color: #1e66ae;">
<a href="http://groups.yahoo.com/group/hackers-il;_ylc=X3oDMTJlazgwbTllBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTM0MTYzNjc4NA--" style="text-decoration: none;">Visit Your Group</a>
</div>
</div>
<div id="ft" style="font-family: Arial; font-size: 11px; margin-top: 5px; padding: 0 2px 0 0; clear: both;">
<a href="http://groups.yahoo.com/;_ylc=X3oDMTJkNWM0NjgxBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxMzQxNjM2Nzg0" style="float: left;"><img src="http://l.yimg.com/a/i/us/yg/logo/us.gif" height="15" width="137" alt="Yahoo! Groups" style="border: 0;"/></a>
<div style="color: #747575; float: right;">Switch to: <a href="mailto:[email protected]?subject=Change Delivery Format: Traditional" style="text-decoration: none;">Text-Only</a>, <a href="mailto:[email protected]?subject=Email Delivery: Digest" class="margin-rt" style="text-decoration: none;">Daily Digest</a> • <a href="mailto:[email protected]?subject=Unsubscribe" style="text-decoration: none;">Unsubscribe</a> • <a href="http://docs.yahoo.com/info/terms/" style="text-decoration: none;">Terms of Use</a></div>
</div>
<!-- |**|end egp html banner|**| -->
</div> <!-- ygrp-msg -->
<!-- Sponsor -->
<!-- |**|begin egp html banner|**| -->
<div id="ygrp-sponsor" style="width:160px; float:right; clear:none; margin:0 0 25px 0; background: #fff;">
<!-- Start Recommendations -->
<div id="ygrp-reco">
</div>
<!-- End Recommendations -->
</div> <!-- |**|end egp html banner|**| -->
<div style="clear:both; color: #FFF; font-size:1px;">.</div>
</div>
<img src="http://geo.yahoo.com/serv?s=97359714/grpId=1857332/grpspId=1705006764/msgId=5185/stime=1341636784/nc1=3848644/nc2=5191954/nc3=4507179" width="1" height="1"> <br>
<div style="color: #fff; height: 0;">__,_._,___</div>
<!--~-|**|PrettyHtmlEnd|**|-~-->
</body>
<!--~-|**|PrettyHtmlStart|**|-~-->
<head>
<style type="text/css">
<!--
#ygrp-mkp {
border: 1px solid #d8d8d8;
font-family: Arial;
margin: 10px 0;
padding: 0 10px;
}
#ygrp-mkp hr {
border: 1px solid #d8d8d8;
}
#ygrp-mkp #hd {
color: #628c2a;
font-size: 85%;
font-weight: 700;
line-height: 122%;
margin: 10px 0;
}
#ygrp-mkp #ads {
margin-bottom: 10px;
}
#ygrp-mkp .ad {
padding: 0 0;
}
#ygrp-mkp .ad p {
margin: 0;
}
#ygrp-mkp .ad a {
color: #0000ff;
text-decoration: none;
}
#ygrp-sponsor #ygrp-lc {
font-family: Arial;
}
#ygrp-sponsor #ygrp-lc #hd {
margin: 10px 0px;
font-weight: 700;
font-size: 78%;
line-height: 122%;
}
#ygrp-sponsor #ygrp-lc .ad {
margin-bottom: 10px;
padding: 0 0;
}
a {
color: #1e66ae;
}
#actions {
font-family: Verdana;
font-size: 11px;
padding: 10px 0;
}
#activity {
background-color: #e0ecee;
float: left;
font-family: Verdana;
font-size: 10px;
padding: 10px;
}
#activity span {
font-weight: 700;
}
#activity span:first-child {
text-transform: uppercase;
}
#activity span a {
color: #5085b6;
text-decoration: none;
}
#activity span span {
color: #ff7900;
}
#activity span .underline {
text-decoration: underline;
}
.attach {
clear: both;
display: table;
font-family: Arial;
font-size: 12px;
padding: 10px 0;
width: 400px;
}
.attach div a {
text-decoration: none;
}
.attach img {
border: none;
padding-right: 5px;
}
.attach label {
display: block;
margin-bottom: 5px;
}
.attach label a {
text-decoration: none;
}
blockquote {
margin: 0 0 0 4px;
}
.bold {
font-family: Arial;
font-size: 13px;
font-weight: 700;
}
.bold a {
text-decoration: none;
}
dd.last p a {
font-family: Verdana;
font-weight: 700;
}
dd.last p span {
margin-right: 10px;
font-family: Verdana;
font-weight: 700;
}
dd.last p span.yshortcuts {
margin-right: 0;
}
div.attach-table div div a {
text-decoration: none;
}
div.attach-table {
width: 400px;
}
div.file-title a, div.file-title a:active, div.file-title a:hover, div.file-title a:visited {
text-decoration: none;
}
div.photo-title a, div.photo-title a:active, div.photo-title a:hover, div.photo-title a:visited {
text-decoration: none;
}
div#ygrp-mlmsg #ygrp-msg p a span.yshortcuts {
font-family: Verdana;
font-size: 10px;
font-weight: normal;
}
.green {
color: #628c2a;
}
.MsoNormal {
margin: 0 0 0 0;
}
o {
font-size: 0;
}
#photos div {
float: left;
width: 72px;
}
#photos div div {
border: 1px solid #666666;
height: 62px;
overflow: hidden;
width: 62px;
}
#photos div label {
color: #666666;
font-size: 10px;
overflow: hidden;
text-align: center;
white-space: nowrap;
width: 64px;
}
#reco-category {
font-size: 77%;
}
#reco-desc {
font-size: 77%;
}
.replbq {
margin: 4px;
}
#ygrp-actbar div a:first-child {
/* border-right: 0px solid #000;*/
margin-right: 2px;
padding-right: 5px;
}
#ygrp-mlmsg {
font-size: 13px;
font-family: Arial, helvetica,clean, sans-serif;
*font-size: small;
*font: x-small;
}
#ygrp-mlmsg table {
font-size: inherit;
font: 100%;
}
#ygrp-mlmsg select, input, textarea {
font: 99% Arial, Helvetica, clean, sans-serif;
}
#ygrp-mlmsg pre, code {
font:115% monospace;
*font-size:100%;
}
#ygrp-mlmsg * {
line-height: 1.22em;
}
#ygrp-mlmsg #logo {
padding-bottom: 10px;
}
#ygrp-mlmsg a {
color: #1E66AE;
}
#ygrp-msg p a {
font-family: Verdana;
}
#ygrp-msg p#attach-count span {
color: #1E66AE;
font-weight: 700;
}
#ygrp-reco #reco-head {
color: #ff7900;
font-weight: 700;
}
#ygrp-reco {
margin-bottom: 20px;
padding: 0px;
}
#ygrp-sponsor #ov li a {
font-size: 130%;
text-decoration: none;
}
#ygrp-sponsor #ov li {
font-size: 77%;
list-style-type: square;
padding: 6px 0;
}
#ygrp-sponsor #ov ul {
margin: 0;
padding: 0 0 0 8px;
}
#ygrp-text {
font-family: Georgia;
}
#ygrp-text p {
margin: 0 0 1em 0;
}
#ygrp-text tt {
font-size: 120%;
}
#ygrp-vital ul li:last-child {
border-right: none !important;
}
-->
</style>
</head>
<!--~-|**|PrettyHtmlEnd|**|-~-->
</html>
<!-- end group email -->
--PKBLb89OSKu99VKAhZpT1ABdnNUiOWnegOUfZLD--