Rosetta Code

Knuth's algorithm S: Difference between revisions

Page Discussion

Knuth's algorithm S (view source)

Revision as of 21:22, 4 November 2017

549 bytes added ,  6 years ago
m
→‎{{header|REXX}}: added/changed comments and whitespace, used a template for the output, used a simpler function for COMMAS, added a header separator.
(Added Rust)
m (→‎{{header|REXX}}: added/changed comments and whitespace, used a template for the output, used a simpler function for COMMAS, added a header separator.)
Line 1,331:
 
=={{header|REXX}}==
<lang rexx>/*REXX program using Knuth's algorithm S (a random sampling N of M items). */
parse arg trials size . /*obtain optional arguments from the CL*/
if trials=='' then| trials=100000 ="," then trials=100000 /*Not specified? Then use the default.*/
if size=='' then| size=="," then 3size= 3 /* " " " " " " */
#.=0 /*initialize frequency counter array. */
do trials /*OK, now let's light this candle. */
call s_of_n_creator size /*create an initial list of N items. */
 
do gener=0 for 10
call s_of_n gener /*call s_of_n with a single decimal dig*/
end /*gener*/
 
do count=1 for size /*let's [↓] examine what SofN generated. */
do _count=!.count 1 for size; _= !.count /*get a decimaldec. digit from the Nth item. */
#._=#._ + 1 /* ··· item, and count it, of course /*bump counter for the decimal digit. */
end /*count*/
end /*trials*/
@= ' trials, and with a size= of '
say hdr=" Using Knuth's algorithm S for " commas(trials) @ || commas(size)": "
say hdr; say copies("═", length(hdr) ) /*display the header and its separator.*/
say
do dig=0 to 9 /* [↓] display the frequency of a dig.*/
say left('',20) "frequency of the" dig 'digit is:' commas(#.dig)
end /*dig*/▼
exit /*stick a fork in it, we're all done. */▼
/*────────────────────────────────────────────────────────────────────────────*/
commas: procedure; parse arg _; n=_'.9'; #=123456789; b=verify(n,#,"M")
e=verify(n, #'0', , verify(n, #"0.", 'M')) - 4
do j=e to b by -3; _=insert(',',_,j); end /*j*/; return _▼
/*────────────────────────────────────────────────────────────────────────────*/
s_of_n: parse arg item; items=items+1 /*get "item", bump the items counter.*/
c=random(1, items) /* [↓] should replace a previous item?*/▼
if c>size then return /*probability isn't good, so skip it. */
_=random(1, size); !._=item /*now, figure out which previous ··· */
return /* ··· item to replace with ITEM.*/▼
/*────────────────────────────────────────────────────────────────────────────*/
s_of_n_creator: parse arg item 1 items /*generate ITEM number of items. */▼
do k=1 for item /*traipse through the first N items. */
!.k=random(0, 9) /*set the Kth item with random digit.*/▼
end /*k*/▼
return /*the piddly stuff is done (for now). */</lang>▼
'''output''' &nbsp; when using the default input of: &nbsp; <tt> 100000 &nbsp; 2 </tt>▼
<pre>▼
Using Knuth's algorithm S for 100,000 trials, and with size=3:▼
 
do dig=0 to 9 frequency of /* [↓] display the 0frequency digitof is:a 29,843dig.*/
say left('', 20) "frequency of the" frequency ofdig the 1 'digit is: 30,083' commas(#.dig)
▲ end /*dig*/
frequency of the 2 digit is: 29,966▼
exit frequency of the 3 digit is: 30 /*stick a fork in it,006 we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
frequency of the 4 digit is: 30,137▼
▲commas: parse arg _; do jjc=elength(_)-3 to b1 by -3; _=insert(',', _,j jc); end /*j*/; return _
frequency of the 5 digit is: 29,833▼
/*──────────────────────────────────────────────────────────────────────────────────────*/
frequency of the 6 digit is: 30,160▼
s_of_n: parse arg item; items=items + 1 /*get "item", frequency ofbump the 7items digit is: 30,182counter.*/
c=random(1, items) frequency of the 8 digit is: 29,941 /* [↓] should replace a previous item?*/
if c>size then return frequency of the 9 digit is: 29 /*probability isn't good,849 so skip it. */
▲ c_=random(1, itemssize); !._=item /*now, [↓]figure out shouldwhich replaceprevious ··· a previous item?*/
▲ return /* ··· item to replace with ITEM.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
▲s_of_n_creator: parse arg item 1 items /*generate ITEM number of items. */
▲exit do k=1 for item /*stick atraipse forkthrough inthe it,first we'reN all doneitems. */
▲ !.k=random(0, 9) /*set the Kth item with random digit.*/
▲ end /*k*/
▲ return /*the piddly stuff is done (for now). */</lang>
▲'''{{out|output''' |text=&nbsp; when using the default input of: &nbsp; &nbsp; <tt> 100000 &nbsp; 2 </tt>}}
▲<pre>
▲ Using Knuth's algorithm S for 100,000 trials, and with a size= of 3:
═════════════════════════════════════════════════════════════════════════
▲ frequency of the 20 digit is: 29,966670
frequency of the 1 digit is: 29,869
▲ frequency of the 42 digit is: 30,137073
frequency of the 3 digit is: 30,076
frequency of the 4 digit is: 29,996
▲ frequency of the 5 digit is: 29,833914
▲ frequency of the 6 digit is: 30,160133
frequency of the 7 digit is: 30,099
frequency of the 8 digit is: 30,036
frequency of the 9 digit is: 30,134
</pre>
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/203131"