Liberty BASIC Programmer's Encyc - RandomOptimalSelection

Operations in a loop. 
<h1>Single-pass random optimal selection.</h1>
<a class="wiki_link" href="/tsh73">tsh73</a>, may 2013 
<img id="wikitext@@toc@@normal" class="WikiMedia WikiMediaToc" title="Table of Contents" src="/site/embedthumbnail/toc/normal?w=225&h=100"/><hr />
<h1>(How come?)</h1>
I encountered this problem in one of my programs. 
I thought solution to be kind of cool, in a nerdy kind of way; but I had a doubt if it’s too obvious to warrant an article of its own. So I checked it on my colleague, a teacher; and she said “I think it’s interesting, go ahead and post it”. So here I am. 
 
<h1>The problem:</h1>
Imagine you have a choosing program, likely involving big (lengthy) search. You are interested in picking just one of “best” solutions; being “best” amounts to having maximum of some criteria – a single number. 
However, beforehand you have no idea what number would it be; more, you have no idea if it would be single solution with maximum criteria or hundreds of them. 
But in case you have several of them, you think it would be nice to pick one of them at random – I mean, with equal probability. (In case you program some game, say Tic-tac-toe, it would make computer opponent play more interesting – instead of picking same response along each path, it would show some variation). (Note: You can easily have first of them or last of them, depending of putting &gt; or &gt;= in your maximum search code; but with equal probability? ) 
 
<h1>Easy (read no-thinking) way</h1>
So. Easy (read no-thinking) way if doing this would require several passes of search loop. 
<ul class="quotelist"><li>1. On the first pass, you determine maximum criteria value (“best”).</li><li>2. On the second pass, you count number of occurrences (Nbest) of that “best” value.</li></ul><ul><li>Then you can dimension array for that value (dim A(Nbest)) 
3. Third pass fill that array with solutions yielding “best” criteria.</li><li>And at last, we can finally generate random number R between 1 and Nbest and return A(R).</li></ul>

<pre class="lb">'problem: 'You have a choosing program, likely involving big (lengthy) search. 'You are interested in picking just one of &quot;best&quot; solutions; 'being &quot;best&quot; amounts to having maximum of some criteria - a single number. 'v.1. Easy (read no-thinking) way 'for now, i 1..N would be search space, b(i) is criteria 'i, so that b(i)= max, is solution (one of). N=100 dim b(N) NN=int(rnd(0)*20)+20 for i = 1 to N b(i)=int(rnd(0)*NN) next print &quot;We have &quot;;N; &quot; integer random numbers.&quot; 'On the first pass, you determine maximum criteria value (&quot;best&quot;). best = -1e40 'so that it would be guaranteed less then maximum for i = 1 to N if b(i)&gt;best then best=b(i) next print &quot;Maximum of them: &quot;; best 'On the second pass, you count number of occurrences (Nbest) of that &quot;best&quot; value. Nbest=0 print &quot;solution&quot;,&quot;value&quot; for i = 1 to N if b(i)=best then Nbest=Nbest+1 print i, b(i) end if next print &quot;----------------------&quot; print &quot;Num of solutions(maxumums) &quot;;Nbest 'Then you can dimension array for that value (dim A(Nbest)) dim a(Nbest) 'Third pass fill that array with solutions yielding &quot;best&quot; criteria. j=0 print &quot;number&quot;,&quot;solution&quot;,&quot;value&quot; for i = 1 to N if b(i)=best then j=j+1 a(j)=i print j, a(j), b(a(j)) end if next print &quot;----------------------&quot; 'And at last, we can finally generate random number R between 1 and Nbest R=int(rnd(0)*Nbest)+1 'and return A(R). print &quot;We choose solution &quot;;a(R);&quot; with value &quot;;b(a(R))</pre>
This approach has one definite value – clarity. Remember? 
Make it work – make it work right – make it work fast, and only in that order! 
But supposed you already at “work right” phase, some speeding up might as well be welcome. We started with “big (lengthy) search”, remember? 
 
<h1>Cutting it 2x</h1>
Currently, our algorithm passes over that lengthy search trice. 
We can rather easily cut it 2x: 
First, we can combine first two phases in one, in a single pass

<pre class="lb">'On the first pass, you determine maximum criteria value (&quot;best&quot;). 'On the second pass, you count number of occurrences (Nbest) of that &quot;best&quot; value. ' combine first two phases in one, in a single pass best = -1e40 'so that it would be guaranteed less then maximum Nbest=0 for i = 1 to N if b(i)=best then Nbest=Nbest+1 end if if b(i)&gt;best then 'order is important: it's too late to check if(b(i)=best) best=b(i) 'after assignment on this line! Nbest=1 end if next print &quot;Maximum of them: &quot;; best print &quot;Num of solutions(maxumums) &quot;;Nbest</pre>
So that leaves us with two passes (of three) 
Second, we can skip that array business altogether. 
We just generate R then run last pass, stopping after hitting R-th best value.

<pre class="lb">'We just generate R then run last pass, stopping after hitting R-th best value. R=int(rnd(0)*Nbest)+1 print &quot;We choose &quot;;R;&quot;-th solution&quot; j=0 print &quot;number&quot;,&quot;solution&quot;,&quot;value&quot; for i = 1 to N if b(i)=best then j=j+1 print j, i, b(i) if j=R then exit for 'stopping after hitting R-th best value end if next print &quot;----------------------&quot; print &quot;We choose solution &quot;;i;&quot; with value &quot;;b(i)</pre>
That will cost us from around 1 (best case, R=1) to around full search pass (worst case, R=Nbest), in average – a half. So we end up with 1½ of a full search. As I promised, 2x cut from three passes :). 
 
<h1>And now, in a single pass</h1>
Could it be made better? 
Well, yes. 
We will do all that in a single pass. 
Here’s how. 
 
Then we hit best value, we could have a counter – how much times we already had that best value? 
<ul><li>If answer is 0, (this is best value and it happened just now), then we just keep it, no question asked.</li><li>If answer is 1, we have N=2 equal values. So we take new value with probability 1/N 
(ha! It just means ½ in our case!), that is, with condition<ul class="quotelist"><li><tt>If rnd(0)&lt;1/N then</tt></li></ul>If condition fails, we will keep old value.</li><li>Likewise, if answer is 2, we have N=3 equal values. We take new value with probability 1/N (1/3 now), else we well keep old value (that happened to be 1st or second best value with equal probability).</li></ul>You get the picture. ;) 
Now, the code.

<pre class="lb">'problem: 'You have a choosing program, likely involving big (lengthy) search. 'You are interested in picking just one of &quot;best&quot; solutions; 'being &quot;best&quot; amounts to having maximum of some criteria - a single number. 'v.3. Single pass solution. 'for now, i 1..N would be search space, b(i) is criteria 'i, so that b(i)= max, is solution (one of). N=100 dim b(N) NN=int(rnd(0)*20)+20 for i = 1 to N b(i)=int(rnd(0)*NN) next print &quot;We have &quot;;N; &quot; integer random numbers.&quot; 'Single pass 'Gets maximum, 'counts number of maximums 'and randomly keeps one of them. best = -1e40 'so that it would be guaranteed less then maximum Nbest=0 solution=0 for i = 1 to N if b(i)=best then Nbest=Nbest+1 'now we have Nbest equal values 'So we take new value with probability 1/Nbest If rnd(1)&lt;1/Nbest then solution=i end if 'else we well keep old value (do nothing) end if if b(i)&gt;best then 'this is best value and it happened just now best=b(i) 'we just keep it, no question asked solution=i Nbest=1 'start counting anew end if next print &quot;Maximum of them: &quot;; best print &quot;Num of solutions(maxumums) &quot;;Nbest print &quot;We choose solution &quot;;solution;&quot; with value &quot;;b(solution)</pre>
As I promised, it all happened along single pass of an algorithm! 
<hr />
<img id="wikitext@@toc@@flat" class="WikiMedia WikiMediaTocFlat" title="Table of Contents" src="/site/embedthumbnail/toc/flat?w=100&h=16"/>