Knuth's algorithm S: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: changed comments and whitespace, used a simpler DO loop index, changed header/title width.) |
|||
| Line 1,496: | Line 1,496: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
<lang rexx>/*REXX program using Knuth's algorithm S (a 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 optional arguments from the CL*/ |
parse arg trials size . /*obtain optional arguments from the CL*/ |
||
if trials=='' | trials=="," then trials= |
if trials=='' | trials=="," then trials= 100000 /*Not specified? Then use the default.*/ |
||
if size=='' | size=="," then size= |
if size=='' | size=="," then size= 3 /* " " " " " " */ |
||
#.= |
#.= 0 /*initialize frequency counter array. */ |
||
do trials /*OK, now let's light this candle. */ |
do trials /*OK, now let's light this candle. */ |
||
call s_of_n_creator size /*create an initial list of N items. */ |
call s_of_n_creator size /*create an initial list of N items. */ |
||
do |
do gen=0 for 10; call s_of_n gen /*call s_of_n with a single decimal dig*/ |
||
| ⚫ | |||
call s_of_n gener /*call s_of_n with a single decimal dig*/ |
|||
| ⚫ | |||
/* [↓] examine what SofN generated. */ |
/* [↓] examine what SofN generated. */ |
||
do count=1 for size; _= !.count /*get a dec. digit from the Nth item. */ |
do count=1 for size; _= !.count /*get a dec. digit from the Nth item. */ |
||
#._=#._ + 1 |
#._= #._ + 1 /*bump counter for the decimal digit. */ |
||
end /*count*/ |
end /*count*/ |
||
end /*trials*/ |
end /*trials*/ |
||
@= ' trials, and with a size of ' |
@= ' trials, and with a size of ' |
||
hdr=" Using Knuth's algorithm S for " commas(trials) @ || commas(size)": " |
hdr= " Using Knuth's algorithm S for " commas(trials) @ || commas(size)": " |
||
say hdr; |
say hdr; say copies("═", length(hdr) ) /*display the header and its separator.*/ |
||
do dig=0 to 9 /* [↓] display the frequency of a dig.*/ |
do dig=0 to 9 /* [↓] display the frequency of a dig.*/ |
||
| Line 1,524: | Line 1,522: | ||
commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _ |
commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
s_of_n: parse arg item; |
s_of_n: parse arg item; items= items + 1 /*get "item", bump the items counter.*/ |
||
if random(1, items)>size then return /*probability isn't good, so skip it. */ |
|||
_= random(1, size); !._= item /*now, figure out which previous ··· */ |
|||
_=random(1, size); !._=item /*now, figure out which previous ··· */ |
|||
return /* ··· item to replace with ITEM.*/ |
return /* ··· item to replace with ITEM.*/ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
s_of_n_creator: parse arg item 1 items /*generate ITEM number of items. */ |
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. */ |
do k=1 for item /*traipse through the first N items. */ |
||
!.k=random(0, 9) |
!.k= random(0, 9) /*set the Kth item with random digit.*/ |
||
end /*k*/ |
end /*k*/ |
||
return /*the piddly stuff is done (for now). */</lang> |
|||
{{out|output|text= when using the default input of: <tt> 100000 2 </tt>}} |
{{out|output|text= when using the default input of: <tt> 100000 2 </tt>}} |
||
<pre> |
<pre> |
||
Using Knuth's algorithm S for 100,000 trials, and with a size of 3: |
|||
═══════════════════════════════════════════════════════════════════════════ |
|||
═════════════════════════════════════════════════════════════════════════ |
|||
frequency of the 0 digit is: 29, |
frequency of the 0 digit is: 29,879 |
||
frequency of the 1 digit is: |
frequency of the 1 digit is: 30,259 |
||
frequency of the 2 digit is: 30, |
frequency of the 2 digit is: 30,254 |
||
frequency of the 3 digit is: |
frequency of the 3 digit is: 29,929 |
||
frequency of the 4 digit is: |
frequency of the 4 digit is: 30,022 |
||
frequency of the 5 digit is: |
frequency of the 5 digit is: 30,010 |
||
frequency of the 6 digit is: |
frequency of the 6 digit is: 29,692 |
||
frequency of the 7 digit is: 30, |
frequency of the 7 digit is: 30,108 |
||
frequency of the 8 digit is: |
frequency of the 8 digit is: 29,976 |
||
frequency of the 9 digit is: |
frequency of the 9 digit is: 29,871 |
||
</pre> |
</pre> |
||