Knuth's algorithm S: Difference between revisions

Content added Content deleted
(→‎{{header|Julia}}: A new entry for Julia)
m (→‎{{header|REXX}}: added/changed whitespace and comments, changed subroutine names.)
Line 1,193: Line 1,193:


=={{header|REXX}}==
=={{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 (a random sampling N of M items). */
parse arg trials size . /*obtain the arguments from C.L. */
parse arg trials size . /*obtain optional arguments from the CL*/
if trials=='' then trials=100000 /*use default if not specified. */
if trials=='' then trials=100000 /*Not specified? Then use the default.*/
if size=='' then size=3 /* " " " " " */
if size=='' then size=3 /* " " " " " " */
#.=0 /*a couple handfuls of counters. */
#.=0 /*initialize an array of freq counters.*/
do trials /*OK, let's light this candle. */
do trials /*OK, now let's light this candle. */
call s_of_n_creator size /*create initial list of n items.*/
call SofN_creator size /*create initial list of N items. */


do gener=0 for 10 /*and then call SofN for each dig*/
do gener=0 for 10 /*and then call SofN for each digit. */
call s_of_n gener /*call s_of_n with a single dig*/
call SofN gener /*call SofN with a single decimal dig*/
end /*gener*/
end /*gener*/


do count=1 for size /*let's see what s_of_n wroth. */
do count=1 for size /*let's examine what SofN generated. */
_=!.count /*get a digit from the Nth item, */
_=!.count /*get a digit from the Nth item, and */
#._=#._+1 /* ... and count it, of course. */
#._=#._+1 /* ··· count it, of course. */
end /*count*/
end /*count*/
end /*trials*/
end /*trials*/


say "Using Knuth's algorihm S for" comma(trials) 'trials, and with size='comma(size)":"
say "Using Knuth's algorithm S for" commas(trials),
⚫
'trials, and with size='commas(size)":"; say
say
do dig=0 to 9 /*show & tell time for frequency.*/
do dig=0 to 9 /* [↓] display the frequency of a dig.*/
say copies(' ',15) "frequency of the" dig 'digit is:' comma(#.dig)
say left('',15) "frequency of the" dig 'digit is:' commas(#.dig)
end /*dig*/
end /*dig*/
exit /*stick a fork in it, we're done.*/
exit /*stick a fork in it, we're all done. */
/*────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────S_OF_N_CREATOR subroutine───────────*/
s_of_n_creator: parse arg item 1 items /*generate ITEM number of items*/
SofN_creator: parse arg item 1 items /*generate ITEM number of items. */
do k=1 for item /*traipse through the 1st N items*/
do k=1 for item /*traipse through the firs N items. */
!.k=random(0,9) /*set the Kth item with rand dig.*/
!.k=random(0, 9) /*set the Kth item with random digit.*/
end /*k*/
end /*k*/
return /*out piddly work is done for now*/
return /*the piddly stuff is done for now. */
/*────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────S_OF_N subroutine───────────────────*/
s_of_n: parse arg item; items=items+1 /*get "item", bump items counter.*/
SofN: parse arg item; items=items+1 /*get "item", bump the items counter.*/
c=random(1,items) /*should we replace a prev item? */
c=random(1, items) /*should we replace a previous item? */
if c>size then return /*probability isn't good, skip it*/
if c>size then return /*probability isn't good, so skip it. */
_=random(1,size) /*now, figure out which previous */
_=random(1, size) /*now, figure out which previous ··· */
!._=item /* ... item to replace with ITEM.*/
!._=item /* ··· item to replace with ITEM. */
return
⚫
return /*and back to the caller we go. */
/*────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────COMMA subroutine────────────────────*/
comma: procedure; parse arg _,c,p,t;arg ,cu;c=word(c ",",1)
commas: procedure; parse arg _; c=","; p=3; n=_'.9'; #=123456789
⚫
b=verify(n, #, "M"); e=verify(n, #'0', , verify(n, #"0.", 'M') ) - p - 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 _
do j=e to b by -p; _=insert(c, _, j); end; return _</lang>
⚫
'''output''' &nbsp; when using the default input of: &nbsp; <tt> 100000 &nbsp; 2 </tt>
n=_'.9'; #=123456789; k=0; if o<0 then do; b=verify(_,' '); if b==0 then return _
<pre>
e=length(_)-verify(reverse(_),' ')+1; end; else do; b=verify(n,#,"M")
⚫
e=verify(n,#'0',,verify(n,#"0.",'M'))-p-1; end
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="overflow:scroll">
Using Knuth's algorihm S for 100,000 trials, and with size=3:
Using Knuth's algorihm S for 100,000 trials, and with size=3:


Retrieved from "https://rosettacode.org/wiki/Knuth%27s_algorithm_S"