How to resolve the algorithm Knuth's algorithm S step by step in the Elena programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Knuth's algorithm S step by step in the Elena 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 Elena programming language

Source code in the elena programming language

import system'dynamic;
import extensions;
import system'routines;
import system'collections;
 
extension algorithmOp
{
    s_of_n()
    {
        var counter := new Integer();
        var n := self;
 
        ^ new ArrayList().mixInto(new
        {
            eval(i)
            {
                counter.append:1;

                if (weak self.Length < n)
                { 
                    weak self.append:i 
                }
                else
                { 
                    if(randomGenerator.nextInt:counter < n)
                        { weak self[randomGenerator.nextInt:n] := i }
                };

                ^ weak self.Value
            }
        })
    }
}
 
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()
}

  

You may also check:How to resolve the algorithm Update a configuration file step by step in the Racket programming language
You may also check:How to resolve the algorithm Sierpinski triangle step by step in the Pascal programming language
You may also check:How to resolve the algorithm Cumulative standard deviation step by step in the BBC BASIC programming language
You may also check:How to resolve the algorithm 24 game step by step in the Yabasic programming language
You may also check:How to resolve the algorithm Arithmetic/Complex step by step in the Yabasic programming language