Knuth's algorithm S: Difference between revisions
added RPL
m (→{{header|REXX}}: changed (back again) the subroutine/function names to conform to the Rosetta Code task requirements.) |
(added RPL) |
||
(50 intermediate revisions by 22 users not shown) | |||
Line 2:
This is a method of randomly sampling n items from a set of M items, with equal probability; where M >= n and M, the number of items is unknown until the end.
This means that the equal probability sampling should be maintained for all successive items > n as they become available (although the content of successive samples can change).
;The algorithm:
;The Task:
:::# Use the s_of_n_creator with n == 3 to generate an s_of_n.
:::# call s_of_n with each of the digits 0 to 9 in order, keeping the returned three digits of its random sampling from its last call with argument item=9.
Note: A class taking n and generating a callable instance/function might also be used.
;Reference:
* The Art of Computer Programming, Vol 2, 3.4.2 p.142
;Related tasks:
* [[One of n lines in a file]]
* [[Accumulator factory]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">T S_of_n_creator
Int n
i = 0
[Int] sample
F (n)
.n = n
F ()(item)
.i++
I .i <= .n
.sample.append(item)
E I random:(.i) < .n
.sample[random:(.n)] = item
V binarr = [0] * 10
V items = Array(0..9)
print(‘Single run samples for n = 3:’)
V s_of_n = S_of_n_creator(3)
L(item) items
s_of_n(item)
print(‘ Item: #. -> sample: #.’.format(item, s_of_n.sample))
L 100000
s_of_n = S_of_n_creator(3)
L(item) items
s_of_n(item)
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 ")))</syntaxhighlight>
{{out}}
<pre>
Single run samples for n = 3:
Item: 0 -> sample: [0]
Item: 1 -> sample: [0, 1]
Item: 2 -> sample: [0, 1, 2]
Item: 3 -> sample: [3, 1, 2]
Item: 4 -> sample: [3, 1, 2]
Item: 5 -> sample: [3, 1, 2]
Item: 6 -> sample: [3, 6, 2]
Item: 7 -> sample: [3, 7, 2]
Item: 8 -> sample: [3, 7, 2]
Item: 9 -> sample: [3, 7, 2]
Test item frequencies for 100000 runs:
0:30229
1:30182
2:29981
3:30058
4:29749
5:29952
6:30102
7:29955
8:29917
9:29875
</pre>
=={{header|Ada}}==
Line 28 ⟶ 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 39 ⟶ 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 80 ⟶ 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 117 ⟶ 184:
& Natural'Image(Result(Dig)) & "; ");
end loop;
end Test_S_Of_N;</
A sample output:
Line 126 ⟶ 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 179 ⟶ 246:
a$ += STR$(a%(i%)) + ", "
NEXT
= LEFT$(LEFT$(a$)) + "]"</
'''Output:'''
<pre>
Line 209 ⟶ 276:
=={{header|C}}==
Instead of returning a closure we set the environment in a structure:
<syntaxhighlight lang="c">#include <stdlib.h>
#include <stdio.h>
#include <string.h>
Line 281 ⟶ 347:
puts("");
return 0;
}</
Sample output:
<pre> 29980 29746 30111 30034 29922 29720 30222 30183 29995 30087</pre>
=={{header|C++}}==
{{works with|C++11}}
<
#include <functional>
#include <vector>
Line 320 ⟶ 389:
std::cout << x << std::endl;
return 0;
}</
{{out}}
<pre>
Line 336 ⟶ 405:
Class-based version:
<
#include <vector>
#include <cstdlib>
Line 373 ⟶ 442:
std::cout << bin[i] << std::endl;
return 0;
}</
=={{header|Clojure}}==
Line 379 ⟶ 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 398 ⟶ 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 442 ⟶ 511:
for digit in range
console.log digit, counts[digit]
</syntaxhighlight>
output
<syntaxhighlight lang="text">
> coffee knuth_sample.coffee
0 29899
Line 456 ⟶ 525:
8 29976
9 30255
</syntaxhighlight>
=={{header|Common Lisp}}==
<
(let ((sample (make-array n :initial-element nil))
(i 0))
Line 486 ⟶ 554:
(princ (algorithm-s))
</
=={{header|D}}==
<
auto sofN_creator(in int n) {
Line 518 ⟶ 586:
}
writefln("Item counts for %d runs:\n%s", nRuns, bin);
}</
{{out}}
<pre>Item counts for 100000 runs:
Line 524 ⟶ 592:
===Faster Version===
<
struct SOfN(size_t n) {
Line 553 ⟶ 621:
}
writefln("Item counts for %d runs:\n%s", nRuns, bin);
}</
=={{header|Elena}}==
ELENA 6.x :
{
var n := self;
^ new ArrayList().mixInto(new
{
eval(i)
{
if (weak self.Length <
{
}
}
}
public program()
{
var bin := Array.allocate(10).populate::(n => new Integer());
for(int trial := 0; trial < 10000; trial += 1)
{
var s_of_n := 3.s_of_n();
for(int n := 0; n < 10; n += 1)
{
var sample := s_of_n.eval(n);
if (n == 9)
{ sample.forEach::(i){ bin[i].append(1) } }
}
};
console.printLine(bin).readChar()
}</syntaxhighlight>
{{out}}
<pre>
3001,3052,3033,2973,2981,3060,3003,2975,2959,2963
</pre>
=={{header|Elixir}}==
<syntaxhighlight lang="elixir">
defmodule Knuth do
def s_of_n_creator(n), do: {n, 1, []}
def s_of_n({n, i, ys}, x) do
cond
i <=
:rand.uniform(i) <= n ->
{n, i+1, List.replace_at(ys, :rand.uniform(n)-1, x)}
true -> {n, i+1, ys}
end
end
results = Enum.reduce(1..100000, %{}, fn _, freq ->
{_, _, xs} = Enum.reduce(1..10, Knuth.s_of_n_creator(3), fn x, s ->
Knuth.s_of_n(s, x)
end)
Enum.reduce(xs, freq, fn x, freq ->
Map.put(freq, x, (freq[x] || 0) + 1)
end)
end)
IO.inspect results
</syntaxhighlight>
Output:
<pre>%{1 => 30138, 2 => 29980, 3 => 29992, 4 => 29975, 5 => 30110, 6 => 29825,
7 => 29896, 8 => 30188, 9 => 29898, 10 => 29998}</pre>
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
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)
let s_of_n<'n> = s_of_n_creator 3
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>
using an input array -> [|(0, 30162); (1, 30151); (2, 29894); (3, 29766); (4, 30117); (5, 29976); (6, 29916); (7, 29994); (8, 29890); (9, 30134)|]
using an input list -> [|(0, 29936); (1, 29973); (2, 29880); (3, 30160); (4, 30126); (5, 30123); (6, 30062); (7, 30053); (8, 29892); (9, 29795)|]
</pre>
=={{header|Go}}==
<
import (
Line 648 ⟶ 766:
}
fmt.Println(freq)
}</
Output:
<pre>
[30075 29955 30024 30095 30031 30018 29973 29642 30156 30031]
</pre>
=={{header|Haskell}}==
{{libheader|containers}}
{{libheader|MonadRandom}}
{{libheader|random}}
{{libheader|mtl}}
<syntaxhighlight lang="haskell">
import Control.Monad.Random
import Control.Monad.State
import qualified Data.Map as M
import System.Random
-- s_of_n_creator :: Int -> a -> RandT StdGen (State (Int, [a])) [a]
s_of_n_creator :: Int -> a -> StateT (Int, [a]) (Rand StdGen) [a]
s_of_n_creator n v = do
(i, vs) <- get
let i' = i + 1
if i' <= n
then do
let vs' = v : vs
put (i', vs')
pure vs'
else do
j <- getRandomR (1, i')
if j > n
then do
put (i', vs)
pure vs
else do
k <- getRandomR (0, n - 1)
let (f, (_ : b)) = splitAt k vs
vs' = v : f ++ b
put (i', vs')
pure vs'
sample :: Int -> Rand StdGen [Int]
sample n =
let s_of_n = s_of_n_creator n
in snd <$> execStateT (traverse s_of_n [0 .. 9 :: Int]) (0, [])
incEach :: (Ord a, Num b) => M.Map a b -> [a] -> M.Map a b
incEach m ks = foldl (\m' k -> M.insertWith (+) k 1 m') m ks
sampleInc :: Int -> M.Map Int Double -> Rand StdGen (M.Map Int Double)
sampleInc n m = do
s <- sample n
pure $ incEach m s
main :: IO ()
main = do
let counts = M.empty :: M.Map Int Double
n = 100000
gen <- getStdGen
counts <- evalRandIO $ foldM (\c _ -> sampleInc 3 c) M.empty [1 .. n]
print (fmap (/ n) counts)
</syntaxhighlight>
=={{header|Icon}} and {{header|Unicon}}==
Line 663 ⟶ 839:
not a function. In Unicon, the calling syntax for this
co-expression is indistinguishable from that of a function.
<
procedure main(A)
Line 686 ⟶ 862:
}
}
end</
and a sample run:
<pre>->kas
Line 705 ⟶ 881:
Note that this approach introduces heavy inefficiencies, to achieve information hiding.
<syntaxhighlight lang="j">s_of_n_creator=: 1 :0
ctx=: conew&'inefficient' m
s_of_n__ctx
)
coclass'inefficient'
create=:3 :0
N=: y
Line 714 ⟶ 895:
s_of_n=:3 :0
K=: K+1
if. N>:#ITEMS do.
ITEMS=: ITEMS,y
else.
if. (N%K)>?0 do.
ITEMS=: ((
else.
ITEMS
Line 724 ⟶ 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).
Also, we have <code>s_of_n</code> which is a method of that class. It increments K and appends to the list, respecting the random value replacement requirement, once the list has reached the required length.
Finally, we have <code>s_of_n_creator</code> which is not a method of that class, but which will create an object of that class and return the resulting s_of_n method.
Required example:
<
nl=. conl 1
s3_of_n=. 3 s_of_n_creator
Line 742 ⟶ 924:
(~.,._1 + #/.~) (i.10),,D=:run"0 i.1e5
0
1
2
3
4
5
6
7
8
9 29868</syntaxhighlight>
Here, we have each of our digits along with how many times each appeared in a result from <code>run</code>.
Explanation of <code>run</code>:
First, we get a snapshot of the existing objects in <code>nl</code>.
Then, we get our s3_of_n which is a method in a new object.
Then we run that method on each of the values 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9, keeping only the values from the last run, this will be the result of the run.
Then we delete any objects which did not previously exist.
Finally return our result.
=={{header|Java}}==
A class-based solution:
<
class SOfN<T> {
private static final Random rand = new Random();
private List<T> sample;
private int i = 0;
private int n;
public SOfN(int _n) {
}
public List<T> process(T item) {
if (++i <= n) {
sample.add(item);
}
}
}
public class AlgorithmS {
public static void main(String[] args) {
for (int i = 0; i < 9; i++) s_of_n.process(i);
for (int s : s_of_n.process(9)) bin[s]++;
}
System.out.println(Arrays.toString(bin));
}
}</
Sample output:
<pre>[
Alternative solution without using an explicitly named type; instead using an anonymous class implementing a generic "function" interface:
<
interface Function<S, T> {
public T call(S x);
}
public class AlgorithmS {
private static final Random rand = new Random();
public static <T> Function<T, List<T>> s_of_n_creator(final int n) {
if (++i <= n) {
sample.add(item);
} else if (rand.nextInt(i) < n) {
}
return sample;
}
}
public static void main(String[] args) {
for (int i = 0; i < 9; i++) s_of_n.call(i);
}
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}}==
<syntaxhighlight lang="julia">using Printf
function makesofn(n::Integer)
buf = Vector{typeof(n)}(0)
i = 0
return function sofn(item)
i += 1
if i
push!(buf, item)
else
j = rand(1:i)
if j
end
return buf
end
end
nhist = zeros(Int, 10)
for _ in 1:10^5
kas = makesofn(3)
for j in 0:8 kas(j) end
for k
end
println("Simulating sof3(0:9) 100000 times:")
for (i, c) in enumerate(nhist)
end</syntaxhighlight>
{{out}}
<pre>Simulating sof3(0:9) 100000 times:
0 → 29795
1 → 29947
2 → 30227
3 → 30212
4 → 29763
5 → 29960
6 → 29809
7 → 30215
8 → 29948
9 → 30124</pre>
=={{header|Kotlin}}==
{{trans|Java}}
Class based solution:
<syntaxhighlight lang="scala">// version 1.2.51
import java.util.Random
val rand = Random()
class SOfN<T>(val n: Int) {
private val sample = ArrayList<T>(n)
private var i = 0
fun process(item: T): List<T> {
if (++i <= n)
sample.add(item)
else if (rand.nextInt(i) < n)
sample[rand.nextInt(n)] = item
return sample
}
}
fun main(args: Array<String>) {
val bin = IntArray(10)
(1..100_000).forEach {
val sOfn = SOfN<Int>(3)
for (d in 0..8) sOfn.process(d)
for (s in sOfn.process(9)) bin[s]++
}
println(bin.contentToString())
}</syntaxhighlight>
Sample output:
<pre>
[29981, 29845, 29933, 30139, 30051, 30039, 29702, 30218, 30199, 29893]
</pre>
Alternative function based solution:
<syntaxhighlight lang="scala">// version 1.2.51
import java.util.Random
val rand = Random()
fun <T> SOfNCreator(n: Int): (T) -> List<T> {
val sample = ArrayList<T>(n)
var i = 0
return {
if (++i <= n)
sample.add(it)
else if (rand.nextInt(i) < n)
sample[rand.nextInt(n)] = it
sample
}
}
fun main(args: Array<String>) {
val bin = IntArray(10)
(1..100_000).forEach {
val sOfn = SOfNCreator<Int>(3)
for (d in 0..8) sOfn(d)
for (s in sOfn(9)) bin[s]++
}
println(bin.contentToString())
}</syntaxhighlight>
Sample output:
<pre>
[30172, 29856, 30132, 29884, 29818, 30220, 29900, 30069, 29869, 30080]
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[sofncreator]
sofncreator[n_] := Module[{sample, i},
sample = {};
i = 0;
Return[
Function[{item},
i++;
If[i <= n,
AppendTo[sample, item]
,
If[RandomInteger[{1, i}] <= n,
sample[[RandomInteger[{1, n}]]] = item
]
];
sample
]
]
]
bin = ConstantArray[0, 10];
items = Range[10];
sofn = sofncreator[3];
Do[
sample = sofn[item];
Print[" Item: ", item, " -> sample: " , sample]
,
{item, items}
]
Do[
sofn = sofncreator[3];
Do[
sample = sofn[item]
,
{item, items}
];
Do[
bin[[s]] += 1
,
{s, sample}
]
,
{trial, 100000}
];
{Range[Length[bin]], bin} // Transpose // Grid</syntaxhighlight>
{{out}}
<pre> Item: 1 -> sample: {1}
Item: 2 -> sample: {1,2}
Item: 3 -> sample: {1,2,3}
Item: 4 -> sample: {4,2,3}
Item: 5 -> sample: {5,2,3}
Item: 6 -> sample: {5,6,3}
Item: 7 -> sample: {7,6,3}
Item: 8 -> sample: {7,6,3}
Item: 9 -> sample: {7,6,3}
Item: 10 -> sample: {7,10,3}
1 29732
2 30055
3 30059
4 29787
5 30067
6 30123
7 30136
8 30056
9 29949
10 30036</pre>
=={{header|Nim}}==
<syntaxhighlight lang="nim">import random
func sOfNCreator[T](n: Positive): proc(item: T): seq[T] =
var sample = newSeqOfCap[T](n)
var i = 0
result = proc(item: T): seq[T] =
inc i
if i <= n:
sample.add(item)
elif rand(1..i) <= n:
sample[rand(n - 1)] = item
sample
when isMainModule:
randomize()
echo "Digits counts for 100_000 runs:"
var hist: array[10, Natural]
for _ in 1..100_000:
let sOfN = sOfNCreator[Natural](3)
for i in 0..8:
discard sOfN(i)
for val in sOfN(9):
inc hist[val]
for n, count in hist:
echo n, ": ", count</syntaxhighlight>
{{out}}
<pre>Digits counts for 100_000 runs:
0: 30092
1: 29906
2: 29956
3: 29896
4: 30151
5: 30000
6: 30267
7: 29853
8: 30186
9: 29693</pre>
=={{header|Objective-C}}==
{{works with|Mac OS X|10.6+}}
Uses blocks
<
typedef NSArray *(^SOfN)(id);
Line 926 ⟶ 1,362:
}
return 0;
}</
Log:
Line 936 ⟶ 1,372:
=={{header|OCaml}}==
<
let i = ref 0
and sample = ref [| |] in
Line 950 ⟶ 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 960 ⟶ 1,396:
done;
Array.iter (Printf.printf " %d") results;
print_newline ()</
Output:
Line 968 ⟶ 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 982 ⟶ 1,418:
);
v
};</
Output:
Line 988 ⟶ 1,424:
=={{header|Perl}}==
<
sub s_of_n_creator {
Line 1,022 ⟶ 1,458:
}
print "@bin\n";
</syntaxhighlight>
;Sample output:
<pre>30003 29923 30192 30164 29994 29976 29935 29860 30040 29913</pre>
=={{header|Phix}}==
{{trans|C}}
Phix does not support closures, but they are easy enough to emulate using {routine_id,environment}.<br>
Obviously the direct call (as commented out) is inevitably going to be marginally faster, and<br>
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.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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>
<span style="color: #008080;">function</span> <span style="color: #000000;">s_of_n</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">env</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">item</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">env</span><span style="color: #0000FF;">[</span><span style="color: #000000;">I</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">env</span><span style="color: #0000FF;">[</span><span style="color: #000000;">SAMPLE</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">env</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">env</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">env</span><span style="color: #0000FF;">[</span><span style="color: #000000;">I</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">env</span><span style="color: #0000FF;">[</span><span style="color: #000000;">SAMPLE</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">item</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">rnd</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">env</span><span style="color: #0000FF;">[</span><span style="color: #000000;">SAMPLE</span><span style="color: #0000FF;">][</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">item</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">env</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">s_of_n_creator</span><span style="color: #0000FF;">(</span><span style="color: #004080;">int</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">s_of_n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">invoke</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">env</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">args</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">env</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">call_func</span><span style="color: #0000FF;">(</span><span style="color: #000000;">env</span><span style="color: #0000FF;">[</span><span style="color: #000000;">RID</span><span style="color: #0000FF;">],</span><span style="color: #7060A8;">prepend</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">args</span><span style="color: #0000FF;">),</span><span style="color: #000000;">env</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">env</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">items</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">env</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s_of_n_creator</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">items</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">-- env = s_of_n(env,items[i])</span>
<span style="color: #000000;">env</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">invoke</span><span style="color: #0000FF;">(</span><span style="color: #000000;">env</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">items</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">env</span><span style="color: #0000FF;">[</span><span style="color: #000000;">SAMPLE</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">items_set</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">frequencies</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">items_set</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">100000</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">items_set</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">fdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">frequencies</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fdx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">frequencies</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{29631,30097,29737,30252,29774,30147,29901,30042,30204,30215}
</pre>
Note that s_of_n_creator() must match {RID, I, SAMPLE}. You might instead prefer (taking the appropriate care not to miss any!):
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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>
<span style="color: #008080;">function</span> <span style="color: #000000;">s_of_n_creator</span><span style="color: #0000FF;">(</span><span style="color: #004080;">int</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">closure</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">CLOSURE_LEN</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">closure</span><span style="color: #0000FF;">[</span><span style="color: #000000;">RID</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">routine_id</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"s_of_n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">closure</span><span style="color: #0000FF;">[</span><span style="color: #000000;">I</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">closure</span><span style="color: #0000FF;">[</span><span style="color: #000000;">SAMPLE</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">closure</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</syntaxhighlight>-->
=={{header|PHP}}==
{{works with|PHP|5.3+}}
<
function s_of_n_creator($n) {
$sample = array();
Line 1,087 ⟶ 1,564:
}
print_r($bin);
?></
;Sample output:
Line 1,105 ⟶ 1,582:
=={{header|PicoLisp}}==
<
(curry (@N (I . 0) (Res)) (Item)
(cond
Line 1,117 ⟶ 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,123 ⟶ 1,600:
=={{header|Python}}==
{{works with|Python|3.x}}
<
def s_of_n_creator(n):
Line 1,156 ⟶ 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,185 ⟶ 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,200 ⟶ 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,225 ⟶ 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,238 ⟶ 1,715:
9 29777</pre>
=={{header|
(formerly Perl 6)
<syntaxhighlight lang="raku" line>sub s_of_n_creator($n) {
my (@sample, $i);
-> $item {
elsif $i.rand < $n { @sample[$n.rand] = $item }
@sample
}
}
my @bin;
for ^100000 {
my &s_of_n = s_of_n_creator 3;
sink .&s_of_n for ^9;
@bin[$_]++ for s_of_n 9;
}
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.*/
if size=='' |
#.= 0 /*initialize frequency counter array. */
call s_of_n_creator size /*create an initial list of N items. */
do gen=0 for 10; call s_of_n gen /*call s_of_n with a single decimal dig*/
end /*gen*/
/* [↓] examine what SofN generated. */
end /*trials*/
hdr= " Using Knuth's algorithm S for " commas(trials) @ || commas(size)": "
say hdr; say copies("═", length(hdr) ) /*display the header and its separator.*/
do dig=0 to 9
say right("frequency of the", 37) dig
end /*dig*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _
/*──────────────────────────────────────────────────────────────────────────────────────*/
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 ··· */
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). */</syntaxhighlight>
{{out|output|text= when using the default input of: <tt> 100000 2 </tt>}}
<pre>
Using Knuth's algorithm S for 100,000 trials, and with a size
═══════════════════════════════════════════════════════════════════════════
frequency of the 0 digit is: 29,879
frequency of the 1 digit is: 30,259
frequency of the 2 digit is: 30,254
frequency of the 3 digit is: 29,929
frequency of the 4 digit is: 30,022
frequency of the 5 digit is: 30,010
frequency of the 6 digit is: 29,692
frequency of the 7 digit is: 30,108
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,320 ⟶ 1,846:
end
(0..9).each {|digit| puts "#{digit}\t#{frequency[digit]}"}</
Example
<pre>0 29850
Line 1,333 ⟶ 1,858:
8 29953
9 29852</pre>
=={{header|Rust}}==
{{libheader|rand 0.3}}
<syntaxhighlight lang="rust">use rand::{Rng,weak_rng};
struct SofN<R: Rng+Sized, T> {
rng: R,
sample: Vec<T>,
i: usize,
n: usize,
}
impl<R: Rng, T> SofN<R, T> {
fn new(rng: R, n: usize) -> Self {
SofN{rng, sample: Vec::new(), i: 0, n}
}
fn add(&mut self, item: T) {
self.i += 1;
if self.i <= self.n {
self.sample.push(item);
} else if self.rng.gen_range(0, self.i) < self.n {
self.sample[self.rng.gen_range(0, self.n)] = item;
}
}
fn sample(&self) -> &Vec<T> {
&self.sample
}
}
pub fn main() {
const MAX: usize = 10;
let mut bin: [i32; MAX] = Default::default();
for _ in 0..100000 {
let mut s_of_n = SofN::new(weak_rng(), 3);
for i in 0..MAX { s_of_n.add(i); }
for s in s_of_n.sample() {
bin[*s] += 1;
}
}
for (i, x) in bin.iter().enumerate() {
println!("frequency of {}: {}", i, x);
}
}</syntaxhighlight>
{{out}}
<pre>
frequency of 0: 29883
frequency of 1: 29901
frequency of 2: 29896
frequency of 3: 30029
frequency of 4: 30017
frequency of 5: 29850
frequency of 6: 30139
frequency of 7: 30252
frequency of 8: 30030
frequency of 9: 30003
</pre>
=={{header|Scala}}==
===Imperative (Ugly and side effects)===
{{trans|Java}}
<syntaxhighlight lang="scala">import java.util
import scala.util.Random
object KnuthsAlgorithmS extends App {
import scala.collection.JavaConverters._
val (n, rand, bin) = (3, Random, new Array[Int](10))
for (_ <- 0 until 100000) {
val sample = new util.ArrayList[Int](n)
for (item <- 0 until 10) {
if (item < n) sample.add(item)
else if (rand.nextInt(item + 1) < n)
sample.asScala(rand.nextInt(n)) = item
}
for (s <- sample.asScala.toList) bin(s) += 1
}
println(bin.mkString("[", ", ", "]"))
}</syntaxhighlight>
{{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|
<
var i = 0
var sample = []
Line 1,364 ⟶ 1,980:
}
say bin;</
{{out}}
<pre>
Line 1,371 ⟶ 1,987:
=={{header|Swift}}==
<
func s_of_n_creator<T>(n: Int) -> T -> [T] {
Line 1,398 ⟶ 2,014:
}
}
println(bin)</
{{out}}
<pre>
Line 1,405 ⟶ 2,021:
=={{header|Tcl}}==
<
oo::class create SofN {
Line 1,433 ⟶ 2,049:
}
}
parray freq</
Sample output:<pre>
freq(0) = 29812
Line 1,445 ⟶ 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}}
<syntaxhighlight lang="wren">import "random" for Random
var r = Random.new()
var sOfNCreator = Fn.new { |n|
var s = List.filled(n, 0)
var next = 0
var m = n
return Fn.new { |item|
if (next < n) {
s[next] = item
next = next + 1
} else {
m = m + 1
if (r.int(m) < n) {
var t = r.int(n)
s[t] = item
if (next <= t) next = t + 1
}
}
return s
}
}
var freq = List.filled(10, 0)
for (r in 0...1e5) {
var sOfN = sOfNCreator.call(3)
for (d in 48...57) sOfN.call(d)
for (d in sOfN.call(57)) {
freq[d - 48] = freq[d - 48] + 1
}
}
System.print(freq)</syntaxhighlight>
{{out}}
Sample run:
<pre>
[29842, 30051, 29878, 30178, 29731, 30089, 30070, 29939, 30058, 30164]
</pre>
=={{header|zkl}}==
<
fcn(item,ri,N,samples){
i:=ri.inc(); // 1,2,3,4,...
Line 1,455 ⟶ 2,152:
samples
}.fp1(Ref(1),n,L())
}</
One run:
<
[0..9].pump(List,s3,"copy").println();</
{{out}}
<pre>
Line 1,464 ⟶ 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>
|