Knuth's algorithm S: Difference between revisions

* [[Accumulator factory]]

<br><br>

 

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

 

Sample output:

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

import extensions;

import system'routines;

eval(i)

{

 

{

}

else

{

};

 

}

})

public program()

{

{

var s_of_n := 3.s_of_n();

{

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,

 

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

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)

{{out}}

<pre>

 

=={{header|Go}}==

 

import (

}

fmt.Println(freq)

Output:

<pre>

{{libheader|mtl}}

 

import Control.Monad.Random

import Control.Monad.State

counts <- evalRandIO $ foldM (\c _ -> sampleInc 3 c) M.empty [1 .. n]

print (fmap (/ n) counts)

 

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

System.out.println(Arrays.toString(bin));

}

 

Sample output:

 

Alternative solution without using an explicitly named type; instead using an anonymous class implementing a generic "function" interface:

interface Function<S, T> {

System.out.println(Arrays.toString(bin));

}

 

Sample output:

 

<pre>[29965, 30178, 29956, 29957, 30016, 30114, 29977, 29996, 29982, 29859]</pre>

 

=={{header|Julia}}==

 

function makesofn(n::Integer)

for (i, c) in enumerate(nhist)

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

 

{{out}}

{{trans|Java}}

Class based solution:

 

import java.util.Random

}

println(bin.contentToString())

Sample output:

<pre>

 

Alternative function based solution:

 

import java.util.Random

}

println(bin.contentToString())

 

Sample output:

[30172, 29856, 30132, 29884, 29818, 30220, 29900, 30069, 29869, 30080]

</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:

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.

{{out}}

<pre>

</pre>

Note that s_of_n_creator() must match {RID, I, SAMPLE}. You might instead prefer (taking the appropriate care not to miss any!):

 

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

=={{header|Raku}}==

(formerly Perl 6)

-> $item {

}

}

 

my @bin;

for ^100000 {

}

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

!.k= random(0, 9) /*set the Kth item with random digit.*/

end /*k*/

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

<pre>

frequency of the 8 digit is: 29,976

frequency of the 9 digit is: 29,871

</pre>

 

=={{header|Ruby}}==

Using a closure

sample = []

i = 0

end

 

Example

<pre>0 29850

{{libheader|rand 0.3}}

 

 

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

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

}

 

{{out}}

===Imperative (Ugly and side effects)===

{{trans|Java}}

import scala.util.Random

 

 

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}}==

var i = 0

var sample = []

}

 

{{out}}

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