Rosetta Code

Knuth's algorithm S: Difference between revisions

Page Discussion

Knuth's algorithm S (view source)

Revision as of 20:32, 18 October 2012

16 bytes removed ,  11 years ago
m
→‎{{header|REXX}}: changed indentation, added/changed comments, simplified two subroutines. -- ~~~~
(→‎{{header|REXX}}: added the REXX language. -- ~~~~)
m (→‎{{header|REXX}}: changed indentation, added/changed comments, simplified two subroutines. -- ~~~~)
Line 971:
 
=={{header|REXX}}==
<lang rexx>/*REXX program using Knuth's algorithm S (random sampling n of M items).*/▼
<lang rexx>
▲/*REXX program using Knuth's algorithm S (random sampling n of M items).*/
 
parse arg trials size . /*obtain the arguments from C.L. */
if trials=='' then trials=100000 /*use default if not specified. */
if size=='' then size=3 /* " " " " " */
#.=0 /*a couple handfuls of counters. */
do trials _=!.count /*getOK, alet's digitlight fromthis thecandle. Nth item. */▼
call s_of_n_creator size /*create initial list of n items.*/
 
do trials do gener=0 for 10 /*OK, let'sand lightthen thiscall candle.SofN for each dig*/
call s_of_n_creators_of_n gener size /*createcall s_of_n initial listwith ofa nsingle items.dig*/
end end /*countgener*/▼
 
do genercount=01 for 10 size /*andlet's thensee callwhat SofN fors_of_n eachwroth. dig*/
call s_of_n gener_=!.count /*callget a s_of_ndigit from withthe aNth singleitem, dig*/
end #._=#._+1 /*gener ... and count it, of course. */
end /*trialscount*/▼
end /*ktrials*/▼
 
say "Using Knuth's algorihm S for" comma(trials) 'trials, and with size=',comma(size)":"▼
do count=1 for size /*let's see what s_of_n wroth. */
▲ _=!.count /*get a digit from the Nth item. */
#._=#._+1 /* ... and count it, of course. */▼
▲ end /*count*/
 
▲ end /*trials*/
 
▲say "Using Knuth's algorihm S for" comma(trials) 'trials, and with',
"size="comma(size)':'
say
do dig=0 to 9 /*show & tell time for frequency.*/
say copies(' ',15) "frequency of the" dig 'digit is:' comma(#.dig)
end /*dig*/
▲exit #._=#._+1 /*stick ...a andfork countin it, ofwe're coursedone. */
exit
/*──────────────────────────────────S_OF_N_CREATOR subroutine───────────*/
 
s_of_n_creator: parse arg item 1 items /*generate ITEM number of items*/
/*─────────────────────────────────────S_OF_N_CREATOR subroutine────────*/
s_of_n_creator: parse arg do k=1 for item /*generate traipse ITEMthrough the number1st ofN items*/
do k=1 for item !.k=random(0,9) /*traipseset throughthe theKth item 1stwith Nrand itemsdig.*/
!.k=random(0,9) end /*set the Kth item with rand dig.k*/
▲ end /*k*/
items=item /*also, keep track of # of items.*/
return /*out piddly work is done for now*/
/*──────────────────────────────────S_OF_N subroutine───────────────────*/
 
/*─────────────────────────────────────S_OF_N subroutine────────────────*/
s_of_n: parse arg item; items=items+1 /*get "item", bump items counter.*/
c=random(1,items) /*should we replace a prev item? */
if c>size then return /*probability isn't good, skip it*/
_=random(1,size) /*now, figure out which previous */
!._=item /* ... item to replace with ITEM. */
return /*and back to the caller we go. */
/*──────────────────────────────────COMMA subroutine────────────────────*/
 
/*─────────────────────────────────────subroutines for commatization────*/
comma: procedure; parse arg _,c,p,t;arg ,cu;c=word(c ",",1)
if cu=='BLANK' then c=' '; o=word(p 3,1); p=abs(o); t=word(t 999999999,1)
if \datatype(p,'W') | \datatype(t,'W') | p==0 | arg()>4 then return _
n=_'.9'; #=123456789; k=0; returnif comma_o<0 then do; b=verify(_,' '); if b==0 then return _
e=length(_)-verify(reverse(_),' ')+1; end; else do; b=verify(n,#,"M")
 
comma_: if o<0 then do; b e=verify(_n,#' 0',,verify(n,#"0.",'M'))-p-1; if b==0 then return _end
do j=e to b by -p while k<t; _=lengthinsert(c,_)-verify(reverse(_),' 'j); k=k+1; end; elsereturn do; b=verify(n,#,"M")_</lang>
Output '''output''' when using the default input of: <tt> 100000 2 </tt>▼
e=verify(n,#'0',,verify(n,#"0.",'M'))-p-1; end
<pre style="height:35ex;overflow:scroll">▼
do j=e to b by -p while k<t; _=insert(c,_,j); k=k+1; end; return _
</lang>
▲Output when using the default input of: <tt> 100000 2 </tt>
▲<pre style="height:35ex;overflow:scroll">
Using Knuth's algorihm S for 100,000 trials, and with size=3:
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/203089"