Knuth's algorithm S: Difference between revisions

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:

 

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

 

* [[One of n lines in a file]]

* [[Accumulator factory]]

 

=={{header|Ada}}==

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;

function Result return Item_Array;

 

 

Here is the implementation of that package:

 

 

package body S_Of_N_Creator is

D_Rnd.Reset(D_Gen); -- at package instantiation, initialize rnd-generators

F_Rnd.Reset(F_Gen);

 

The main program:

 

 

procedure Test_S_Of_N is

& Natural'Image(Result(Dig)) & "; ");

end loop;

 

A sample output:

{{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:"

a$ += STR$(a%(i%)) + ", "

NEXT

'''Output:'''

<pre>

 

=={{header|C}}==

Instead of returning a closure we set the environment in a structure:

#include <stdio.h>

#include <string.h>

puts("");

return 0;

 

=={{header|C++}}==

{{works with|C++11}}

#include <functional>

#include <vector>

std::cout << x << std::endl;

return 0;

{{out}}

<pre>

 

Class-based version:

#include <vector>

#include <cstdlib>

std::cout << bin[i] << std::endl;

return 0;

 

=={{header|Clojure}}==

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)]

sort

println)

Sample output:

 

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]

 

=={{header|CoffeeScript}}==

s_of_n_creator = (n) ->

arr = []

for digit in range

console.log digit, counts[digit]

output

> coffee knuth_sample.coffee

0 29899

8 29976

9 30255

 

=={{header|Common Lisp}}==

(let ((sample (make-array n :initial-element nil))

(i 0))

 

(princ (algorithm-s))

 

=={{header|D}}==

 

auto sofN_creator(in int n) {

}

writefln("Item counts for %d runs:\n%s", nRuns, bin);

{{out}}

<pre>Item counts for 100000 runs:

 

===Faster Version===

 

struct SOfN(size_t n) {

}

writefln("Item counts for %d runs:\n%s", nRuns, bin);

 

=={{header|Elena}}==

extension algorithmOp

{

{

 

if (n == 9)

{{out}}

<pre>

</pre>

 

=={{header|Elixir}}==

defmodule Knuth do

def s_of_n_creator(n), do: {n, 1, []}

 

IO.inspect results

Output:

<pre>%{1 => 30138, 2 => 29980, 3 => 29992, 4 => 29975, 5 => 30110, 6 => 29825,

7 => 29896, 8 => 30188, 9 => 29898, 10 => 29998}</pre>

 

=={{header|Go}}==

 

import (

}

fmt.Println(freq)

Output:

<pre>

[30075 29955 30024 30095 30031 30018 29973 29642 30156 30031]

</pre>

 

=={{header|Icon}} and {{header|Unicon}}==

not a function. In Unicon, the calling syntax for this

co-expression is indistinguishable from that of a function.

 

procedure main(A)

}

}

and a sample run:

<pre>->kas

Note that this approach introduces heavy inefficiencies, to achieve information hiding.

 

ctx=: conew&'inefficient' m

s_of_n__ctx

end.

)

 

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).

Required example:

 

nl=. conl 1

s3_of_n=. 3 s_of_n_creator

7 36416

8 33172

 

Here, we have each of our digits along with how many times each appeared in a result from <code>run</code>.

=={{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) {

sample.add(item);

}

}

public class AlgorithmS {

public static void main(String[] args) {

}

 

 

 

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) {

}

public static void main(String[] args) {

}

 

=={{header|Julia}}==

 

buf = Vector{typeof(n)}(0)

i = 0

for (i, c) in enumerate(nhist)

@printf("%5d → %5d\n", i-1, c)

 

{{out}}

=={{header|Kotlin}}==

{{trans|Java}}

 

import java.util.Random

 

class SOfN<T>(val n: Int) {

private var i = 0

 

if (++i <= n)

sample.add(item)

}

}

fun main(args: Array<String>) {

val bin = IntArray(10)

(1..100_000).forEach {

val sOfn = SOfN<Int>(3)

}

println(bin.contentToString())

Sample output:

<pre>

</pre>

 

=={{header|Objective-C}}==

{{works with|Mac OS X|10.6+}}

Uses blocks

 

typedef NSArray *(^SOfN)(id);

}

return 0;

 

Log:

=={{header|OCaml}}==

 

let i = ref 0

and sample = ref [| |] in

 

let () =

let n = 3 in

let num_items = 10 in

let items_set = Array.init num_items (fun i -> i) in

for i = 1 to 100_000 do

let res = test n items_set in

done;

Array.iter (Printf.printf " %d") results;

 

Output:

=={{header|PARI/GP}}==

{{improve|PARI/GP|Does not return a function.}}

my(u=vector(n,i,i));

for(i=n+1,#v,

);

v

 

Output:

 

=={{header|Perl}}==

 

sub s_of_n_creator {

}

print "@bin\n";

 

;Sample output:

<pre>30003 29923 30192 30164 29994 29976 29935 29860 30040 29913</pre>

 

 

=={{header|PHP}}==

{{works with|PHP|5.3+}}

function s_of_n_creator($n) {

$sample = array();

}

print_r($bin);

 

;Sample output:

 

=={{header|PicoLisp}}==

(curry (@N (I . 0) (Res)) (Item)

(cond

(for I (mapc S_of_n (0 1 2 3 4 5 6 7 8 9))

(inc (nth Freq (inc I))) ) ) )

Output:

<pre>-> (30003 29941 29918 30255 29848 29875 30056 29839 30174 30091)</pre>

=={{header|Python}}==

{{works with|Python|3.x}}

 

def s_of_n_creator(n):

bin[s] += 1

print("\nTest item frequencies for 100000 runs:\n ",

 

;Sample output:

===Python Class based version===

Only a slight change creates the following class-based implementation:

def __init__(self, n):

self.n = n

# Keep item

sample[randrange(n)] = item

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)

(for ([d sample]) (vector-set! counts d (add1 (vector-ref counts d)))))

 

Output:

<pre>0 30117

8 29940

9 29777</pre>

 

=={{header|REXX}}==

parse arg trials size . /*obtain optional arguments from the CL*/

do trials /*OK, now let's light this candle. */

call s_of_n_creator size /*create an initial list of N items. */

 

/* [↓] examine what SofN generated. */

do count=1 for size; _= !.count /*get a dec. digit from the Nth item. */

end /*count*/

end /*trials*/

@= ' trials, and with a size of '

 

do dig=0 to 9 /* [↓] display the frequency of a 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 _

/*──────────────────────────────────────────────────────────────────────────────────────*/

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. */

end /*k*/

{{out|output|text=&nbsp; when using the default input of: &nbsp; &nbsp; <tt> 100000 &nbsp; 2 </tt>}}

<pre>

</pre>

 

=={{header|Ruby}}==

Using a closure

sample = []

i = 0

end

 

Example

<pre>0 29850

8 29953

9 29852</pre>

 

=={{header|Rust}}==

{{libheader|rand 0.3}}

 

 

struct SofN<R: Rng+Sized, T> {

println!("frequency of {}: {}", i, x);

}

 

{{out}}

frequency of 8: 30030

frequency of 9: 30003

</pre>

 

=={{header|Swift}}==

 

func s_of_n_creator<T>(n: Int) -> T -> [T] {

}

}

{{out}}

<pre>

 

=={{header|Tcl}}==

 

oo::class create SofN {

}

}

Sample output:<pre>

freq(0) = 29812

freq(8) = 30060

freq(9) = 29824

</pre>

 

=={{header|zkl}}==

fcn(item,ri,N,samples){

i:=ri.inc(); // 1,2,3,4,...

samples

}.fp1(Ref(1),n,L())

One run:

{{out}}

<pre>

</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();

{{out}}

<pre>L("10.00%","9.98%","10.00%","9.99%","10.00%","9.98%","10.01%","10.04%","9.98%","10.02%")</pre>