How to resolve the algorithm Knuth's algorithm S step by step in the Icon and Unicon programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Knuth's algorithm S step by step in the Icon and Unicon programming language

Table of Contents

Problem Statement

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

Note: A class taking n and generating a callable instance/function might also be used.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Knuth's algorithm S step by step in the Icon and Unicon programming language

Source code in the icon programming language

import Utils

procedure main(A)
    freq := table(0)
    every 1 to (\A[2] | 100000)\1 do {
        s_of_n := s_of_n_creator(\A[1] | 3)
        every sample := s_of_n(0 to 9)
        every freq[!sample] +:= 1
        }
    every write(i := 0 to 9,": ",right(freq[i],6))
end

procedure s_of_n_creator(n)
    items := []
    itemCnt := 0.0
    return makeProc {
               repeat {
                   item := (items@&source)[1]
                   itemCnt +:= 1
                   if *items < n then put(items, item)
                   else if ?0 < (n/itemCnt) then ?items := item
                   }
               }
end


  

You may also check:How to resolve the algorithm Formatted numeric output step by step in the Free Pascal programming language
You may also check:How to resolve the algorithm Roman numerals/Encode step by step in the Clojure programming language
You may also check:How to resolve the algorithm CSV data manipulation step by step in the BASIC programming language
You may also check:How to resolve the algorithm Write float arrays to a text file step by step in the Scala programming language
You may also check:How to resolve the algorithm Short-circuit evaluation step by step in the BASIC programming language