Knuth's algorithm S: Difference between revisions
added RPL
m (→{{header|Phix}}: added syntax colouring, marked p2js compatible) |
(added RPL) |
||
(10 intermediate revisions by 8 users not shown) | |||
Line 33:
{{trans|Python}}
<
Int n
i = 0
Line 62:
L(s) s_of_n.sample
binarr[s]++
print("\nTest item frequencies for 100000 runs:\n "(enumerate(binarr).map((i, x) -> ‘#.:#.’.format(i, x)).join("\n ")))</
{{out}}
Line 95:
Instead of defining a function S_of_N_Creator, we define a generic packgage with that name. The generic parameters are N (=Sample_Size) and the type of the items to be sampled:
<
Sample_Size: Positive;
type Item_Type is private;
Line 106:
function Result return Item_Array;
end S_Of_N_Creator;</
Here is the implementation of that package:
<
package body S_Of_N_Creator is
Line 147:
D_Rnd.Reset(D_Gen); -- at package instantiation, initialize rnd-generators
F_Rnd.Reset(F_Gen);
end S_Of_N_Creator;</
The main program:
<
procedure Test_S_Of_N is
Line 184:
& Natural'Image(Result(Dig)) & "; ");
end loop;
end Test_S_Of_N;</
A sample output:
Line 193:
{{works with|BBC BASIC for Windows}}
At each of the 100000 repetitions not only is a new function created but also new copies of its PRIVATE variables '''index%''' and '''samples%()'''. Creating such a large number of variables at run-time impacts adversely on execution speed and isn't to be recommended, other than to meet the artificial requirements of the task.
<
PRINT "Single run samples for n = 3:"
Line 246:
a$ += STR$(a%(i%)) + ", "
NEXT
= LEFT$(LEFT$(a$)) + "]"</
'''Output:'''
<pre>
Line 276:
=={{header|C}}==
Instead of returning a closure we set the environment in a structure:
<
#include <stdio.h>
#include <string.h>
Line 347:
puts("");
return 0;
}</
Sample output:
Line 354:
=={{header|C++}}==
{{works with|C++11}}
<
#include <functional>
#include <vector>
Line 389:
std::cout << x << std::endl;
return 0;
}</
{{out}}
<pre>
Line 405:
Class-based version:
<
#include <vector>
#include <cstdlib>
Line 442:
std::cout << bin[i] << std::endl;
return 0;
}</
=={{header|Clojure}}==
Line 448:
Here the accumulator state is the current sample and the number of items processed.
This function is then used in a ''reduce'' call with an initial state and a list of items.
<
(fn [[sample iprev] item]
(let [i (inc iprev)]
Line 467:
sort
println)
</syntaxhighlight>
Sample output:
<syntaxhighlight lang="text">([0 29924] [1 30053] [2 30018] [3 29765] [4 29974] [5 30225] [6 30082] [7 29996] [8 30128] [9 29835])</
If we really need a stateful (thread safe!) function for some reason, we can get it like this:
<
(let [state (atom [[] 0])
s-of-n-fn (s-of-n-fn-creator n)]
(fn [item]
(first (swap! state s-of-n-fn item)))))</
=={{header|CoffeeScript}}==
<
s_of_n_creator = (n) ->
arr = []
Line 511:
for digit in range
console.log digit, counts[digit]
</syntaxhighlight>
output
<syntaxhighlight lang="text">
> coffee knuth_sample.coffee
0 29899
Line 525:
8 29976
9 30255
</syntaxhighlight>
=={{header|Common Lisp}}==
<
(let ((sample (make-array n :initial-element nil))
(i 0))
Line 554:
(princ (algorithm-s))
</
=={{header|D}}==
<
auto sofN_creator(in int n) {
Line 586:
}
writefln("Item counts for %d runs:\n%s", nRuns, bin);
}</
{{out}}
<pre>Item counts for 100000 runs:
Line 592:
===Faster Version===
<
struct SOfN(size_t n) {
Line 621:
}
writefln("Item counts for %d runs:\n%s", nRuns, bin);
}</
=={{header|Elena}}==
ELENA
<
import extensions;
import system'routines;
Line 641:
eval(i)
{
counter.append
if (
{
}
else
{
if(randomGenerator.nextInt
{
};
^
}
})
Line 661:
public program()
{
var bin := Array.allocate(10).populate::(n => new Integer());
for(int trial := 0
{
var s_of_n := 3.s_of_n();
for(int n := 0
{
var sample := s_of_n.eval
if (n == 9)
{ sample.forEach::(i){ bin[i].append
}
};
console.printLine
}</
{{out}}
<pre>
3001,3052,3033,2973,2981,3060,3003,2975,2959,2963
</pre>
=={{header|Elixir}}==
<
defmodule Knuth do
def s_of_n_creator(n), do: {n, 1, []}
Line 709:
IO.inspect results
</syntaxhighlight>
Output:
<pre>%{1 => 30138, 2 => 29980, 3 => 29992, 4 => 29975, 5 => 30110, 6 => 29825,
Line 715:
=={{header|F_Sharp|F#}}==
<
let N=System.Random 23 //Nigel Galloway: August 7th., 2018
let s_of_n_creator i = fun g->Seq.fold(fun (n:_[]) g->if N.Next()%(g+1)>i-1 then n else n.[N.Next()%i]<-g;n) (Array.ofSeq (Seq.take i g)) (Seq.skip i g)
Line 721:
printfn "using an input array -> %A" (List.init 100000 (fun _->s_of_n [|0..9|]) |> Array.concat |> Array.countBy id |> Array.sort)
printfn "using an input list -> %A" (List.init 100000 (fun _->s_of_n [0..9]) |> Array.concat |> Array.countBy id |> Array.sort)
</syntaxhighlight>
{{out}}
<pre>
Line 729:
=={{header|Go}}==
<
import (
Line 766:
}
fmt.Println(freq)
}</
Output:
<pre>
Line 779:
{{libheader|mtl}}
<
import Control.Monad.Random
import Control.Monad.State
Line 828:
counts <- evalRandIO $ foldM (\c _ -> sampleInc 3 c) M.empty [1 .. n]
print (fmap (/ n) counts)
</syntaxhighlight>
=={{header|Icon}} and {{header|Unicon}}==
Line 839:
not a function. In Unicon, the calling syntax for this
co-expression is indistinguishable from that of a function.
<
procedure main(A)
Line 862:
}
}
end</
and a sample run:
<pre>->kas
Line 881:
Note that this approach introduces heavy inefficiencies, to achieve information hiding.
<
ctx=: conew&'inefficient' m
s_of_n__ctx
Line 905:
end.
)
</syntaxhighlight>
Explanation: <code>create</code> is the constructor for the class named <code>inefficient</code> and it initializes three properties: <code>N</code> (our initial value), <code>ITEMS</code> (an initially empty list) and <code>K</code> (a counter which is initially 0).
Line 915:
Required example:
<
nl=. conl 1
s3_of_n=. 3 s_of_n_creator
Line 933:
7 36416
8 33172
9 29868</
Here, we have each of our digits along with how many times each appeared in a result from <code>run</code>.
Line 951:
=={{header|Java}}==
A class-based solution:
<
class SOfN<T> {
Line 985:
System.out.println(Arrays.toString(bin));
}
}</
Sample output:
Line 992:
Alternative solution without using an explicitly named type; instead using an anonymous class implementing a generic "function" interface:
<
interface Function<S, T> {
Line 1,024:
System.out.println(Arrays.toString(bin));
}
}</
Sample output:
<pre>[29965, 30178, 29956, 29957, 30016, 30114, 29977, 29996, 29982, 29859]</pre>
=={{header|jq}}==
'''Adapted from [[#Wren]]'''
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq'''.
jq does not support functions that return functions,
so we adopt the approach taken for example by the [[#C|C]] entry.
Specifically, following the [[#Wren|Wren]] model, the closure variables
are encapsulated in a JSON object of the form {n, s, next, m},
which is initially
<pre>
{n: $n, s: [range(0;$n)|0], next: 0, m: $n}
</pre>
where $n is the maximum sample size.
In the following, /dev/random is used as a source of entropy.
In a bash or bash-like environment, a suitable invocation would
be as follows:
<pre>
< /dev/random tr -cd '0-9' | fold -w 1 | jq -Mcnr algorithm-s.jq
</pre>
'''algorithm-s.jq'''
<syntaxhighlight lang=jq>
# Output: a PRN in range(0; .)
def prn:
if . == 1 then 0
else . as $n
| (($n-1)|tostring|length) as $w
| [limit($w; inputs)] | join("") | tonumber
| if . < $n then . else ($n | prn) end
end;
# Input and output: {n, s, next, m}
# The initial input should be
# {n: $n, s: [range(0;$n)|0], next: 0, m: $n}
# where $n is the maximum sample size.
def sOfN(items):
if (.next < .n)
then .s[.next] = items
| .next += 1
else .m += 1
| if ((.m | prn) < .n)
then (.n | prn) as $t
| .s[$t] = items
| if .next <= $t
then .next = $t + 1
else .
end
else .
end
end;
def task($iterations):
def dim($n): [range(0;$n)|0];
def init($n): {n: $n, s: dim($n), next: 0, m: $n };
reduce range(0; $iterations) as $r ( {freq: dim(10) };
reduce range(48; 57) as $d (. + init(3); sOfN($d) )
| reduce sOfN(57).s[] as $d (.;
.freq[$d - 48] += 1) )
| .freq ;
task(1e5)
</syntaxhighlight>
{{output}}
<pre>
[30008,29988,29827,30101,30308,30005,29808,29851,30218,29886]
</pre>
=={{header|Julia}}==
<
function makesofn(n::Integer)
Line 1,058 ⟶ 1,129:
for (i, c) in enumerate(nhist)
@printf("%5d → %5d\n", i-1, c)
end</
{{out}}
Line 1,076 ⟶ 1,147:
{{trans|Java}}
Class based solution:
<
import java.util.Random
Line 1,103 ⟶ 1,174:
}
println(bin.contentToString())
}</
Sample output:
<pre>
Line 1,110 ⟶ 1,181:
Alternative function based solution:
<
import java.util.Random
Line 1,136 ⟶ 1,207:
}
println(bin.contentToString())
}</
Sample output:
Line 1,144 ⟶ 1,215:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
sofncreator[n_] := Module[{sample, i},
sample = {};
Line 1,186 ⟶ 1,257:
{trial, 100000}
];
{Range[Length[bin]], bin} // Transpose // Grid</
{{out}}
<pre> Item: 1 -> sample: {1}
Line 1,212 ⟶ 1,283:
=={{header|Nim}}==
<
func sOfNCreator[T](n: Positive): proc(item: T): seq[T] =
Line 1,240 ⟶ 1,311:
for n, count in hist:
echo n, ": ", count</
{{out}}
Line 1,258 ⟶ 1,329:
{{works with|Mac OS X|10.6+}}
Uses blocks
<
typedef NSArray *(^SOfN)(id);
Line 1,291 ⟶ 1,362:
}
return 0;
}</
Log:
Line 1,301 ⟶ 1,372:
=={{header|OCaml}}==
<
let i = ref 0
and sample = ref [| |] in
Line 1,315 ⟶ 1,386:
let () =
Random.self_init ();
let n = 3 in
let num_items = 10 in
let items_set = Array.init num_items (fun i -> i) in
let results = Array.
for i = 1 to 100_000 do
let res = test n items_set in
Line 1,325 ⟶ 1,396:
done;
Array.iter (Printf.printf " %d") results;
print_newline ()</
Output:
Line 1,333 ⟶ 1,404:
=={{header|PARI/GP}}==
{{improve|PARI/GP|Does not return a function.}}
<
my(u=vector(n,i,i));
for(i=n+1,#v,
Line 1,347 ⟶ 1,418:
);
v
};</
Output:
Line 1,353 ⟶ 1,424:
=={{header|Perl}}==
<
sub s_of_n_creator {
Line 1,387 ⟶ 1,458:
}
print "@bin\n";
</syntaxhighlight>
;Sample output:
Line 1,398 ⟶ 1,469:
of course an s_of_n() that operated directly on local vars rather than elements of env, would be faster still.<br>
Not that a mere 100,000 samples takes any method more than a tiny fraction of a second, you understand.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">RID</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">I</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">SAMPLE</span>
Line 1,446 ⟶ 1,517:
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</
{{out}}
<pre>
Line 1,452 ⟶ 1,523:
</pre>
Note that s_of_n_creator() must match {RID, I, SAMPLE}. You might instead prefer (taking the appropriate care not to miss any!):
<!--<
<span style="color: #008080;">enum</span> <span style="color: #000000;">RID</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">I</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">SAMPLE</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">CLOSURE_LEN</span><span style="color: #0000FF;">=$</span>
<span style="color: #0000FF;">...</span>
Line 1,462 ⟶ 1,533:
<span style="color: #008080;">return</span> <span style="color: #000000;">closure</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</
=={{header|PHP}}==
{{works with|PHP|5.3+}}
<
function s_of_n_creator($n) {
$sample = array();
Line 1,493 ⟶ 1,564:
}
print_r($bin);
?></
;Sample output:
Line 1,511 ⟶ 1,582:
=={{header|PicoLisp}}==
<
(curry (@N (I . 0) (Res)) (Item)
(cond
Line 1,523 ⟶ 1,594:
(for I (mapc S_of_n (0 1 2 3 4 5 6 7 8 9))
(inc (nth Freq (inc I))) ) ) )
Freq )</
Output:
<pre>-> (30003 29941 29918 30255 29848 29875 30056 29839 30174 30091)</pre>
Line 1,529 ⟶ 1,600:
=={{header|Python}}==
{{works with|Python|3.x}}
<
def s_of_n_creator(n):
Line 1,562 ⟶ 1,633:
bin[s] += 1
print("\nTest item frequencies for 100000 runs:\n ",
'\n '.join("%i:%i" % x for x in enumerate(bin)))</
;Sample output:
Line 1,591 ⟶ 1,662:
===Python Class based version===
Only a slight change creates the following class-based implementation:
<
def __init__(self, n):
self.n = n
Line 1,606 ⟶ 1,677:
# Keep item
sample[randrange(n)] = item
return sample</
The above can be instantiated as follows after which <code>s_of_n</code> can be called in the same way as it is in the first example where it is a function instead of an instance.
<
=={{header|Racket}}==
<
(define (s-of-n-creator n)
Line 1,631 ⟶ 1,702:
(for ([d sample]) (vector-set! counts d (add1 (vector-ref counts d)))))
(for ([d 10]) (printf "~a ~a\n" d (vector-ref counts d)))</
Output:
<pre>0 30117
Line 1,646 ⟶ 1,717:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
my (@sample, $i);
-> $item {
if ++$i <= $n { @sample.push: $item }
elsif $i.rand <
}
}
my @bin;
for ^100000 {
my &s_of_n = s_of_n_creator
}
say @bin;</syntaxhighlight>
Output:
<pre>29975 30028 30246 30056 30004 29983 29836 29967 29924 29981</pre>
=={{header|REXX}}==
<
parse arg trials size . /*obtain optional arguments from the CL*/
if trials=='' | trials=="," then trials= 100000 /*Not specified? Then use the default.*/
Line 1,713 ⟶ 1,773:
!.k= random(0, 9) /*set the Kth item with random digit.*/
end /*k*/
return /*the piddly stuff is done (for now). */</
{{out|output|text= when using the default input of: <tt> 100000 2 </tt>}}
<pre>
Line 1,728 ⟶ 1,788:
frequency of the 8 digit is: 29,976
frequency of the 9 digit is: 29,871
</pre>
=={{header|RPL}}==
This is an idiomatic adaptation of the algorithm: SCREA initializes 2 persistent variables: S contains the sample and SPAR the algorithm parameters (n and i)
{{works with|RPL|HP49-C}}
« 0 2 →LIST '<span style="color:green">SPAR</span>' STO { } '<span style="color:green">S</span>' STO
» '<span style="color:blue">SCREA</span>' STO
« <span style="color:green">SPAR</span> EVAL
'''CASE'''
DUP2 > '''THEN''' DROP2 '<span style="color:green">S</span>' STO+ '''END'''
/ →NUM RAND ≥ '''THEN''' <span style="color:green">S</span> DUP SIZE RAND * CEIL ROT PUT '<span style="color:green">S</span>' STO '''END'''
DROP '''END'''
'<span style="color:green">SPAR</span>' 2 DUP2 GET 1 + PUT <span style="color:green">S</span>
» '<span style="color:blue">SOFN</span>' STO
« { } → sample
« { 10 } 0 CON
1 1000 '''START'''
3 <span style="color:blue">SCREA</span>
0
0 9 '''FOR''' k
DROP k <span style="color:blue">SOFN</span>
'''NEXT'''
'sample' STO
« sample k POS » 'k' 0 9 1 SEQ
NOT NOT AXL +
'''NEXT'''
» » '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: [ 206. 218. 235. 309. 359. 329. 327. 324. 359. 334. ]
</pre>
=={{header|Ruby}}==
Using a closure
<
sample = []
i = 0
Line 1,754 ⟶ 1,846:
end
(0..9).each {|digit| puts "#{digit}\t#{frequency[digit]}"}</
Example
<pre>0 29850
Line 1,771 ⟶ 1,863:
{{libheader|rand 0.3}}
<
struct SofN<R: Rng+Sized, T> {
Line 1,816 ⟶ 1,908:
println!("frequency of {}: {}", i, x);
}
}</
{{out}}
Line 1,835 ⟶ 1,927:
===Imperative (Ugly and side effects)===
{{trans|Java}}
<
import scala.util.Random
Line 1,855 ⟶ 1,947:
println(bin.mkString("[", ", ", "]"))
}</
{{Out}}See it running in your browser by [https://scalafiddle.io/sf/nlldfXD/0 ScalaFiddle (JavaScript, non JVM)] or by [https://scastie.scala-lang.org/WLaee5H9T72cximqK9gECA Scastie (JVM)].
=={{header|Sidef}}==
{{trans|Raku}}
<
var i = 0
var sample = []
Line 1,888 ⟶ 1,980:
}
say bin;</
{{out}}
<pre>
Line 1,895 ⟶ 1,987:
=={{header|Swift}}==
<
func s_of_n_creator<T>(n: Int) -> T -> [T] {
Line 1,922 ⟶ 2,014:
}
}
println(bin)</
{{out}}
<pre>
Line 1,929 ⟶ 2,021:
=={{header|Tcl}}==
<
oo::class create SofN {
Line 1,957 ⟶ 2,049:
}
}
parray freq</
Sample output:<pre>
freq(0) = 29812
Line 1,969 ⟶ 2,061:
freq(8) = 30060
freq(9) = 29824
</pre>
=={{header|V (Vlang)}}==
{{trans|go}}
<syntaxhighlight lang="v (vlang)">import rand
import rand.seed
fn s_of_ncreator(n int) fn(u8) []u8 {
mut s := []u8{len: 0, cap:n}
mut m := n
return fn[mut s, mut m, n](item u8) []u8 {
if s.len < n {
s << item
} else {
m++
if rand.intn(m) or {0} < n {
s[rand.intn(n) or {0}] = item
}
}
return s
}
}
fn main() {
rand.seed(seed.time_seed_array(2))
mut freq := [10]int{}
for _ in 0..int(1e5) {
s_of_n := s_of_ncreator(3)
for d := '0'[0]; d < '9'[0]; d++ {
s_of_n(d)
}
for d in s_of_n('9'[0]) {
freq[d-'0'[0]]++
}
}
println(freq)
}</syntaxhighlight>
Output:
<pre>
[30131, 30045, 29880, 30178, 29745, 29890, 30150, 30014, 30068, 29899]
</pre>
=={{header|Wren}}==
{{trans|Go}}
<
var r = Random.new()
Line 2,005 ⟶ 2,136:
}
}
System.print(freq)</
{{out}}
Line 2,014 ⟶ 2,145:
=={{header|zkl}}==
<
fcn(item,ri,N,samples){
i:=ri.inc(); // 1,2,3,4,...
Line 2,021 ⟶ 2,152:
samples
}.fp1(Ref(1),n,L())
}</
One run:
<
[0..9].pump(List,s3,"copy").println();</
{{out}}
<pre>
Line 2,030 ⟶ 2,161:
</pre>
100,000 runs:
<
do(0d100_000){
(0).pump(10,Void,s_of_n_creator(3)).apply2('wrap(n){dist[n]=dist[n]+1})
}
N:=dist.sum();
dist.apply('wrap(n){"%.2f%%".fmt(n.toFloat()/N*100)}).println();</
{{out}}
<pre>L("10.00%","9.98%","10.00%","9.99%","10.00%","9.98%","10.01%","10.04%","9.98%","10.02%")</pre>
|