Function

Static Public Summary
public	random(): number Returns a double in the interval [0, 1) using JavaScript Math.random().

Static Private Summary
private	_choice(randint: Function): Function Builds a choice function given a randint function.
private	_fisheryates(randint: Function): Function Sample elements from an array using Fisher-Yates method.
private	_fisheryates_inside_out(randint: Function): Function Shuffle elements of an iterable using an inside-out implementation of the Fisher-Yates method.
private	_randfloat(random: Function): Function Builds a randfloat function given a random number generator.
private	_randint(random: Function): Function Builds a randint function given a random number generator.
private	_randrange(randint: Function): Function Builds a randrange function given a randint function.
private	_shuffle(sample: Function): Function Shuffle the array by sampling the entire array.
private	_waterman(randint: Function): Function Construct a sampling function using Algorithm R due to Alan Waterman (both name and attribution are due to Knuth).

Static Public

public random(): number source

import random from '@randomized/random/src/api/random.js'

Returns a double in the interval [0, 1) using JavaScript Math.random().

Return:

number

Static Private

private _choice(randint: Function): Function source

import _choice from '@randomized/random/src/kernel/_choice.js'

Builds a choice function given a randint function.

Params:

Name	Type	Attribute	Description
randint	Function		The randint function.

Return:

Function

The choice function.

private _fisheryates(randint: Function): Function source

import _fisheryates from '@randomized/random/src/kernel/_fisheryates.js'

Sample elements from an array using Fisher-Yates method.

NOTE: The original description of the algorithm by Fisher and Yates [1] had unnecessary bookkeeping which made the algorithm run in O(n * (j-i)) time. This implementation follows Durstenfeld's [2] and Knuth's [3] descriptions which yield O(n) running time.

For more information see the excellent "Fisher–Yates shuffle" page on Wikipedia [4]. Fisher and Yates description is referred there as "Fisher and Yate's original method" or "pencil-and-paper method". The more efficient implementation described by Durstenfeld and Knuth is referred there as "the modern method".

[1] Fisher, Ronald A.; Yates, Frank (1938). Statistical tables for biological, agricultural and medical research. [2] Durstenfeld, R. (July 1964). "Algorithm 235: Random permutation" [3] Knuth, Donald E. (1969). Seminumerical algorithms. The Art of Computer Programming Volume 2. [4] https://en.wikipedia.org/wiki/Fisher–Yates_shuffle

Params:

Name	Type	Attribute	Description
randint	Function		The randint function.

Return:

Function

The sampling function.

private _fisheryates_inside_out(randint: Function): Function source

import _fisheryates_inside_out from '@randomized/random/src/kernel/_fisheryates_inside_out.js'

Shuffle elements of an iterable using an inside-out implementation of the Fisher-Yates method.

One can observe that if the input contains n elements, the loop has exactly n! possible outcomes: one for the first iteration, two for the second, three for the third, etc., the number of outcomes of a loop being the product of the number of outcomes for each iteration. Given a perfect randint function, each iteration's outcomes are equally likely, and independent of other iterations outcomes. The proof below shows that these outcomes are distinct.

To see that this method yields the correct result (assume perfect randint):

Observe that it is correct when the input is empty.
By induction:
- Induction hypothesis: assume it is correct when the input consists of n elements.
- We almost insert the (n+1)th element at one of the n+1 possible insertion position in the output array. Almost because we move the element that is at the insertion position at the end instead of shifting the elements right of the insertion position to make room for the inserted element.
- Ideally, since we inserted the last element at one of the n+1 positions, we would like that the elements inserted earlier form one of n! permutations uniformly at random after moving the element under the insertion position. This is true because the permutations that we obtain after this move are in one-to-one correspondance with the n! distinct permutations that can be obtained before the move. These are equally likely to be produced by the induction hypothesis.

Params:

Name	Type	Attribute	Description
randint	Function		The randint function.

Return:

Function

The sampling function.

private _randfloat(random: Function): Function source

import _randfloat from '@randomized/random/src/kernel/_randfloat.js'

Builds a randfloat function given a random number generator.

Params:

Name	Type	Attribute	Description
random	Function		A function taking no arguments that returns a double uniformly at random in the interval [0, 1).

Return:

Function

A randfloat function.

private _randint(random: Function): Function source

import _randint from '@randomized/random/src/kernel/_randint.js'

Builds a randint function given a random number generator.

Params:

Name	Type	Attribute	Description
random	Function		A function taking no arguments that returns a double uniformly at random in the interval [0, 1).

Return:

Function

A randint function.

private _randrange(randint: Function): Function source

import _randrange from '@randomized/random/src/kernel/_randrange.js'

Builds a randrange function given a randint function.

Params:

Name	Type	Attribute	Description
randint	Function		The randint function.

Return:

Function

The choice function.

private _shuffle(sample: Function): Function source

import _shuffle from '@randomized/random/src/kernel/_shuffle.js'

Shuffle the array by sampling the entire array.

Params:

Name	Type	Attribute	Description
sample	Function		The sample function.

Return:

Function

The shuffle function.

private _waterman(randint: Function): Function source

import _waterman from '@randomized/random/src/kernel/_waterman.js'

Construct a sampling function using Algorithm R due to Alan Waterman (both name and attribution are due to Knuth).

Params:

Name	Type	Attribute	Description
randint	Function		The randint function.

Return:

Function

The sample function.