Re: Algorithm for randomly choosing a question
Ori Idan <ori-RdxWQVHs3mh9NdQMujDE2GZHpeb/A1Y/@public.gmane.org> Sat, 7 Jul 2012 08:20:57 +0300
| Newsgroups | gmane.culture.hackers.israel |
|---|---|
| Message-ID | <CACyhTREPqAzA8WxbC3EASum+D-MNqm=FAmOagfOVcy41zjZOOg@mail.gmail.com> |
--047d7b339cfb152f2e04c4368e6d
Content-Type: text/plain; charset=ISO-8859-1
>
>
> 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
--047d7b339cfb152f2e04c4368e6d
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/htm=
l4/strict.dtd">
<html>
<head>
</head>
<body style=3D"background-color: #fff;">
<span style=3D"display:none"> </span>
<!--~-|**|PrettyHtmlStartT|**|-~-->
<div id=3D"ygrp-mlmsg" style=3D"position:relative;">
<div id=3D"ygrp-msg" style=3D"z-index: 1;">
<!--~-|**|PrettyHtmlEndT|**|-~-->
<div id=3D"ygrp-text" >
=20=20=20=20=20=20
=20=20=20=20=20=20
<p><div dir=3D"ltr"><div class=3D"gmail_quote"><blockquote class=3D"g=
mail_quote" style=3D"border-left:1px #ccc solid;"><div><div><div><div><p><b=
r>
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 <=3D 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 <=3D 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></p></div></div></div></div></blockquote><div>You don't have to=
keep a list of questions, just a list of numbers where each number represe=
nt a question.</div><div>A question you want to appear twice as much as any=
other, put it twice in the list.</div>
<div>For a question you want to appear 100 times less then any other, use t=
he algorithm you suggested.</div><div><br></div><div>--=A0</div><div>Ori Id=
an</div><div><br></div></div></div>
</p>
</div>
=20=20=20=20=20
<!--~-|**|PrettyHtmlStart|**|-~-->
<div style=3D"color: #fff; height: 0;">__._,_.___</div>
=20=20=20=20=20=20=20=20
=20=20
=20=20=20
<div id=3D"ygrp-actbar" style=3D"clear: both; margin-bottom: 10px; whit=
e-space: nowrap; color: #666; padding-top: 15px;">
<div>
<a href=3D"mailto:ori-RdxWQVHs3mh9NdQMujDE2GZHpeb/A1Y/@public.gmane.org?subject=3DRe%3A%20%5Bhacker=
s-il%5D%20Algorithm%20for%20randomly%20choosing%20a%20question" style=3D"ma=
rgin-right: 0; padding-right: 0;">
Reply to <span style=3D"font-weight: 700;">sender</span></a> |
<a href=3D"mailto:[email protected]?subject=3DRe%3A%20%5Bh=
ackers-il%5D%20Algorithm%20for%20randomly%20choosing%20a%20question">
Reply to <span style=3D"font-weight: 700;">group</span></a> |
<a href=3D"http://groups.yahoo.com/group/hackers-il/post;_ylc=3D=
X3oDMTJwcGJoZGkzBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY=
0BG1zZ0lkAzUxODYEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzQxNjM4NDk4?act=3Dreply&m=
essageNum=3D5186">Reply <span style=3D"font-weight: 700;">via web post</spa=
n></a> |
<a href=3D"http://groups.yahoo.com/group/hackers-il/post;_ylc=
=3DX3oDMTJlNHZmcTUyBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2=
NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTM0MTYzODQ5OA--" style=3D"font-weight:=
700;">Start a New Topic</a>
</div>
<a href=3D"http://groups.yahoo.com/group/hackers-il/message=
/5185;_ylc=3DX3oDMTM0aTZ0OWprBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZA=
MxNzA1MDA2NzY0BG1zZ0lkAzUxODYEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQMxMzQxNjM4NDk4B=
HRwY0lkAzUxODU-">Messages in this topic</a>
(<span style=3D"font-weight: 700;">2</span>)
</div>=20
<!------- Start Nav Bar ------>
<!-- |**|begin egp html banner|**| -->
<div id=3D"ygrp-vital" style=3D"background-color: #e0ecee; font-family: Ver=
dana; font-size: 10px; margin-bottom: 10px; padding: 10px;">
<span id=3D"vithd" style=3D"font-weight: bold; color: #333; text-tran=
sform: uppercase; ">Recent Activity:</span>
<ul style=3D"list-style-type: none; margin: 0; padding: 0; display: inl=
ine;">
<li style=3D"border-right: 1px solid #000; font-weight: 700; di=
splay: inline; padding: 0 5px; margin-left: 0;">
<span class=3D"cat"><a href=3D"http://groups.yahoo.com/group/hackers-=
il/members;_ylc=3DX3oDMTJmOTVlYXFkBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc=
3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZtYnJzBHN0aW1lAzEzNDE2Mzg0OTg-?o=3D6" =
style=3D"text-decoration: none;">New Members</a></span>
<span class=3D"ct" style=3D"color: #ff7900;">1</span>
</li>
</ul>
=20=20=20=20
<div style=3D"clear: both; padding-top: 2px; color: #1e66ae;">
<a href=3D"http://groups.yahoo.com/group/hackers-il;_ylc=3DX3oDMTJlZHZn=
Z2lqBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGw=
Ec2xrA3ZnaHAEc3RpbWUDMTM0MTYzODQ5OA--" style=3D"text-decoration: none;">Vis=
it Your Group</a>
</div>
</div>
=20=20
<div id=3D"ft" style=3D"font-family: Arial; font-size: 11px; margin-top: 5p=
x; padding: 0 2px 0 0; clear: both;">
<a href=3D"http://groups.yahoo.com/;_ylc=3DX3oDMTJkNDM4b2VoBF9TAzk3NDc2NT=
kwBGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZ=
QMxMzQxNjM4NDk4" style=3D"float: left;"><img src=3D"http://l.yimg.com/a/i/u=
s/yg/logo/us.gif" height=3D"15" width=3D"137" alt=3D"Yahoo! Groups" style=
=3D"border: 0;"/></a>
<div style=3D"color: #747575; float: right;">Switch to: <a href=3D"mailto=
:[email protected]?subject=3DChange Delivery Format: T=
raditional" style=3D"text-decoration: none;">Text-Only</a>, <a href=3D"mail=
to:[email protected]?subject=3DEmail Delivery: Digest" clas=
s=3D"margin-rt" style=3D"text-decoration: none;">Daily Digest</a> • <a=
href=3D"mailto:[email protected]?subject=3DUnsubscrib=
e" style=3D"text-decoration: none;">Unsubscribe</a> • <a href=3D"http:=
//docs.yahoo.com/info/terms/" style=3D"text-decoration: none;">Terms of Use=
</a></div>
</div>
<!-- |**|end egp html banner|**| -->
</div> <!-- ygrp-msg -->
<!-- Sponsor -->
<!-- |**|begin egp html banner|**| -->
<div id=3D"ygrp-sponsor" style=3D"width:160px; float:right; clear:none; m=
argin:0 0 25px 0; background: #fff;">
<!-- Start Recommendations -->
<div id=3D"ygrp-reco">
</div>
<!-- End Recommendations -->
</div> <!-- |**|end egp html banner|**| -->
<div style=3D"clear:both; color: #FFF; font-size:1px;">.</div>
</div>
<img src=3D"http://geo.yahoo.com/serv?s=3D97359714/grpId=3D1857332/grpspI=
d=3D1705006764/msgId=3D5186/stime=3D1341638498/nc1=3D4507179/nc2=3D3848644/=
nc3=3D5741398" width=3D"1" height=3D"1"> <br>
<div style=3D"color: #fff; height: 0;">__,_._,___</div>
<!--~-|**|PrettyHtmlEnd|**|-~-->
</body>
<!--~-|**|PrettyHtmlStart|**|-~-->
<head>
<style type=3D"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;
}
=20=20
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.fi=
le-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;
}=20
#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;=20
}=20
-->
</style>
</head>
<!--~-|**|PrettyHtmlEnd|**|-~-->
</html>
<!-- end group email -->
--047d7b339cfb152f2e04c4368e6d--