Pandemonium

Pandemonium is a dead simple JavaScript/TypeScript library providing typical random-related functions such as choice, sample etc.

The library also provides a way to create any of the available functions using a custom random source (seedrandom, for instance).

Installation

npm install --save pandemonium

Usage

Summary

Typical helpers

• choice
• random
• randomBoolean
• randomFloat
• randomIndex
• randomString
• randomUint32
• randomPair
• randomOrderedPair
• shuffle
• shuffleInPlace
• weightedChoice
• weightedRandomIndex

Sampling

n being the number of items in the sampled sequence and k being the number of items to be sampled.

Method	Time	Memory	Note
dangerouslyMutatingSample	O(k)	O(k)	Must be able to mutate given array to work.
fisherYatesSample	O(n)	O(n)	Probably not a good idea.
geometricReservoirSample	O(k*log(n/k))	O(k)	Probably the best way of sampling from a random access data structure.
naiveSample	Ω(k), O(∞)	O(k)	Only useful if k << n.
reservoirSample	O(n)	O(k)	Useful if pulling a sample from a stream.
sampleWithReplacements	O(k)	O(k)	Performant but allows replacements.
samplePairs	Ω(k), O(∞)	O(k)	Variant of naiveSample for unordered pairs.
sampleOrderedPairs	Ω(k), O(∞)	O(k)	Variant of naiveSample for ordered pairs.
weightedReservoirSample	O(n)	O(k)	Variant of reservoirSample working with weighted items.

choice

Function returning a random item from the given array.

1import choice from 'pandemonium/choice';
2// Or
3import {choice} from 'pandemonium';
4
5choice(['apple', 'orange', 'pear']);
6>>> 'orange'
7
8// To create your own function using custom RNG
9import {createChoice} from 'pandemonium/choice';
10
11const customChoice = createChoice(rng);

random

Function returning a random integer between given a & b.

1import random from 'pandemonium/random';
2// Or
3import {random} from 'pandemonium';
4
5random(3, 7);
6>>> 4
7
8// To create your own function using custom RNG
9import {createRandom} from 'pandemonium/random';
10
11const customRandom = createRandom(rng);

randomBoolean

Function returning a random boolean.

1import randomBoolean from 'pandemonium/random-boolean';
2// Or
3import {randomBoolean} from 'pandemonium';
4
5randomBoolean();
6>>> true
7
8// To create your own function using custom RNG
9import {createrandomBoolean} from 'pandemonium/random-boolean';
10
11const customRandomBoolean = createRandomBoolean(rng);

randomFloat

Function returning a random float between given a & b.

1import randomFloat from 'pandemonium/random-float';
2// Or
3import {randomFloat} from 'pandemonium';
4
5randomFloat(-5, 55);
6>>> 6.756482
7
8// To create your own function using custom RNG
9import {createRandomFloat} from 'pandemonium/random-float';
10
11const customRandomFloat = createRandomFloat(rng);

randomIndex

Function returning a random index of the given array.

1import randomIndex from 'pandemonium/random-index';
2// Or
3import {randomIndex} from 'pandemonium';
4
5randomIndex(['apple', 'orange', 'pear']);
6>>> 1
7
8// Alternatively, you can give the array's length instead
9randomIndex(3);
10>>> 2
11
12// To create your own function using custom RNG
13import {createRandomIndex} from 'pandemonium/random-index';
14
15const customRandomIndex = createRandomIndex(rng);

randomString

Function returning a random string.

1import randomString from 'pandemonium/random-string';
2// Or
3import {randomString} from 'pandemonium';
4
5// To generate a string of fixed length
6randomString(5);
7>>> 'gHepM'
8
9// To generate a string of variable length
10randomString(3, 7);
11>>> 'hySf3'
12
13// To create your own function using custom RNG
14import {createRandomString} from 'pandemonium/random-string';
15
16const customRandomString = createRandomString(rng);
17
18// If you need a custom alphabet
19const customRandomString = createRandomString(rng, 'ATGC');

randomUint32

Function returning a random unsigned 32bits number.

1import {randomUint32} from 'pandemonium/random-typed-int';
2// Or
3import {randomUint32} from 'pandemonium';
4
5randomUint32();
6>>> 397536
7
8// To create your own function using custom RNG
9import {createRandomUint32} from 'pandemonium/random-typed-int';
10
11const customRandomUint32 = createRandomUint32(rng);

randomPair

Function returning a random pair from the given array.

Note that this function will return unordered pairs (i.e. [0, 1] and [1, 0] are to be considered the same) and will not return pairs containing twice the same item (i.e. [0, 0]).

1import randomPair from 'pandemonium/random-pair';
2// Or
3import {randomPair} from 'pandemonium';
4
5randomPair(['apple', 'orange', 'pear', 'cherry']);
6>>> ['orange', 'cherry']
7
8// Alternatively, you can give the array's length instead and get a pair of indices
9randomPair(4);
10>>> [1, 3]
11
12// To create your own function using custom RNG
13import {createRandomPair} from 'pandemonium/random-pair';
14
15const customRandomPair = createRandomPair(rng);

randomOrderedPair

Function returning a random ordered pair (i.e. [0, 1] won't be considered to be the same as [1, 0]) from the given array.

1import randomOrderedPair from 'pandemonium/random-ordered-pair';
2// Or
3import {randomOrderedPair} from 'pandemonium';
4
5randomOrderedPair(['apple', 'orange', 'pear', 'cherry']);
6>>> ['cherry', 'apple']
7
8// Alternatively, you can give the array's length instead and get a pair of indices
9randomOrderedPair(4);
10>>> [3, 0]
11
12// To create your own function using custom RNG
13import {createRandomOrderedPair} from 'pandemonium/random-ordered-pair';
14
15const customRandomPair = createRandomOrderedPair(rng);

shuffle

Function returning a shuffled version of the given array using the Fisher-Yates algorithm.

If what you need is to shuffle the original array in place, check out shuffleInPlace.

1import shuffle from 'pandemonium/shuffle';
2// Or
3import {shuffle} from 'pandemonium';
4
5shuffle(['apple', 'orange', 'pear', 'pineapple']);
6>>> ['pear', 'orange', 'apple', 'pineapple']
7
8// To create your own function using custom RNG
9import {createShuffle} from 'pandemonium/shuffle';
10
11const customShuffle = createShuffle(rng);

shuffleInPlace

Function shuffling the given array in place using the Fisher-Yates algorithm.

1import shuffleInPlace from 'pandemonium/shuffle-in-place';
2// Or
3import {shuffleInPlace} from 'pandemonium';
4
5const array = ['apple', 'orange', 'pear', 'pineapple'];
6shuffleInPlace(array);
7
8// Array was mutated:
9array >>> ['pear', 'orange', 'apple', 'pineapple'];
10
11// To create your own function using custom RNG
12import {createShuffleInPlace} from 'pandemonium/shuffle-in-place';
13
14const customShuffleInPlace = createShuffleInPlace(rng);

weightedChoice

Function returning a random item from the given array of weights.

Note that weights don't need to be relative.

1import weightedChoice from 'pandemonium/weighted-choice';
2// Or
3import {weightedChoice} from 'pandemonium';
4
5const array = [.1, .1, .4, .3, .1];
6weightedChoice(array);
7>>> .4
8
9// To create your own function using custom RNG
10import {createWeightedChoice} from 'pandemonium/weighted-choice';
11
12const customWeightedChoice = createWeightedChoice(rng);
13
14// If you have an array of objects
15const customWeightedChoice = createWeightedChoice({
16  rng: rng,
17  getWeight: (item, index) => {
18    return item.weight;
19  }
20});
21
22const array = [{fruit: 'pear', weight: 4}, {fruit: 'apple', weight: 30}];
23customWeightedChoice(array);
24>>> 'apple'
25
26
27// If you intent to call the function multiple times on the same array,
28// you should use the cached version instead:
29import {createCachedWeightedChoice} from 'pandemonium/weighted-choice';
30
31const array = [.1, .1, .4, .3, .1];
32const customWeightedChoice = createCachedWeightedChoice(rng, array);
33
34customWeightedChoice();
35>>> .3

weightedRandomIndex

Function returning a random index from the given array of weights.

Note that weights don't need to be relative.

1import weightedRandomIndex from 'pandemonium/weighted-random-index';
2// Or
3import {weightedRandomIndex} from 'pandemonium';
4
5const array = [.1, .1, .4, .3, .1];
6weightedRandomIndex(array);
7>>> 2
8
9// To create your own function using custom RNG
10import {createWeightedRandomIndex} from 'pandemonium/weighted-random-index';
11
12const customWeightedRandomIndex = createWeightedRandomIndex(rng);
13
14// If you have an array of objects
15const customWeightedRandomIndex = createWeightedRandomIndex({
16  rng: rng,
17  getWeight: (item, index) => {
18    return item.weight;
19  }
20});
21
22const array = [{fruit: 'pear', weight: 4}, {fruit: 'apple', weight: 30}];
23customWeightedRandomIndex(array);
24>>> 1
25
26
27// If you intent to call the function multiple times on the same array,
28// you should use the cached version instead:
29import {createCachedWeightedRandomIndex} from 'pandemonium/weighted-random-index';
30
31const array = [.1, .1, .4, .3, .1];
32const customWeightedRandomIndex = createCachedWeightedRandomIndex(rng, array);
33
34customWeightedRandomIndex();
35>>> 3

dangerouslyMutatingSample

Function returning a random sample of size k from the given array.

This function runs in O(k) time & memory but is somewhat dangerous because it will mutate the given array while performing its Fisher-Yates shuffle before reverting the mutations at the end.

1import dangerouslyMutatingSample from 'pandemonium/dangerously-mutating-sample';
2// Or
3import {dangerouslyMutatingSample} from 'pandemonium';
4
5dangerouslyMutatingSample(2, ['apple', 'orange', 'pear', 'pineapple']);
6>>> ['apple', 'pear']
7
8// To create your own function using custom RNG
9import {createDangerouslyMutatingSample} from 'pandemonium/dangerously-mutating-sample';
10
11const customSample = createDangerouslyMutatingSample(rng);

fisherYatesSample

Function returning a random sample of size k from the given array.

This function uses a partial Fisher-Yates shuffle and therefore runs in O(k) time but must clone the given array to work, which adds O(n) time & memory.

1import fisherYatesSample from 'pandemonium/fisher-yates-sample';
2// Or
3import {fisherYatesSample} from 'pandemonium';
4
5fisherYatesSample(2, ['apple', 'orange', 'pear', 'pineapple']);
6>>> ['apple', 'pear']
7
8// To create your own function using custom RNG
9import {createFisherYatesSample} from 'pandemonium/fisherYatesSample';
10
11const customFisherYatesSample = createFisherYatesSample(rng);

geometricReservoirSample

Function returning a random sample of size k from the given array.

This function runs in O(k * (1 + log(n / k))) time & O(k) memory using "Algorithm L" taken from the following paper:

Li, Kim-Hung. "Reservoir-sampling algorithms of time complexity O(n (1+ log (N/n)))." ACM Transactions on Mathematical Software (TOMS) 20.4 (1994): 481-493.

Note that this function is able to sample indices without requiring you to represent the range of indices in memory.

1import geometricReservoirSample from 'pandemonium/geometric-reservoir-sample';
2// Or
3import {geometricReservoirSample} from 'pandemonium';
4
5geometricReservoirSample(2, ['apple', 'orange', 'pear', 'pineapple']);
6>>> ['apple', 'pear']
7
8// Alternatively, you can pass a length and get a sample of indices back
9geometricReservoirSample(2, 4);
10>>> [0, 2]
11
12// To create your own function using custom RNG
13import {createGeometricReservoirSample} from 'pandemonium/geometric-reservoir-sample';
14
15const customSample = createGeometricReservoirSample(rng);

naiveSample

Function returning a random sample of size k from the given array.

This function works by keeping a Set of the already picked items and choosing a random item in the array until we have the desired k items.

While it is a good pick for cases when k is little compared to the size of your array, this function will see its performance drop really fast when k becomes proportionally bigger.

Note that this function is able to sample indices without requiring you to represent the range of indices in memory.

1import naiveSample from 'pandemonium/naive-sample';
2// Or
3import {naiveSample} from 'pandemonium';
4
5naiveSample(2, ['apple', 'orange', 'pear', 'pineapple']);
6>>> ['apple', 'pear']
7
8// Alternatively, you can pass a length and get a sample of indices back
9naiveSample(2, 4);
10>>> [0, 2]
11
12// To create your own function using custom RNG
13import {createNaiveSample} from 'pandemonium/naive-sample';
14
15const customSample = createNaiveSample(rng);

reservoirSample

Function returning a random sample of size k from the given array.

This function runs in O(n) time and O(k) memory.

A helper class able to work on an arbitrary stream of data that does not need to fit into memory is also available if you need it.

1import reservoirSample from 'pandemonium/reservoir-sample';
2// Or
3import {reservoirSample} from 'pandemonium';
4
5reservoirSample(2, ['apple', 'orange', 'pear', 'pineapple']);
6>>> ['apple', 'pear']
7
8// To create your own function using custom RNG
9import {createReservoirSample} from 'pandemonium/reservoir-sample';
10
11const customReservoirSample = createReservoirSample(rng);
12
13// To use the helper class
14import {ReservoirSampler} from 'pandemonium/reservoir-sample';
15
16// If RNG is not provided, will default to Math.random
17const sampler = new ReservoirSampler(10, rng);
18
19for (const value of lazyIterable) {
20  sampler.process(value);
21}
22
23// To retrieve the sample once every value has been consumed
24const sample = sampler.end();

sampleWithReplacements

Function returning a random sample of size k with replacements from the given array. This prosaically means that an items from the array might occur several times in the resulting sample.

The function runs in both O(k) time & space complexity.

1import sampleWithReplacements from 'pandemonium/sample-with-replacements';
2// Or
3import {sampleWithReplacements} from 'pandemonium';
4
5sampleWithReplacements(3, ['apple', 'orange', 'pear', 'pineapple']);
6>>> ['apple', 'pear', 'apple']
7
8// To create your own function using custom RNG
9import {createSampleWithReplacements} from 'pandemonium/sample-with-replacements';
10
11const customSample = createSampleWithReplacements(rng);

samplePairs

Function returning a random sample of k unique unordered pairs from the given array.

It works by storing a unique key created from the picked pairs, making it a specialized variant of naiveSample.

It is usually quite efficient because when sampling pairs, the total size of the population, being combinatorial, is often magnitudes larger than the size of the sample we need to retrieve.

Note finally that this function is able to sample pairs of indices without requiring you to represent the range of indices in memory.

1import samplePairs from 'pandemonium/sample-pairs';
2// Or
3import {samplePairs} from 'pandemonium';
4
5samplePairs(2, ['apple', 'orange', 'pear', 'pineapple']);
6>>>  [['apple', 'pear'], ['orange', 'pear']]
7
8// Alternatively, you can pass a length and get a sample of pairs of indices
9samplePairs(2, 4);
10>>> [[0, 2], [1, 2]]
11
12// To create your own function using custom RNG
13import {createSamplePairs} from 'pandemonium/sample-pairs';
14
15const customSamplePairs = createSamplePairs(rng);

sampleOrderedPairs

Function returning a random sample of k unique ordered pairs from the given array.

It works by storing a unique key created from the picked pairs, making it a specialized variant of naiveSample.

It is usually quite efficient because when sampling pairs, the total size of the population, being combinatorial, is often magnitudes larger than the size of the sample we need to retrieve.

Note finally that this function is able to sample pairs of indices without requiring you to represent the range of indices in memory.

1import sampleOrderedPairs from 'pandemonium/sample-pairs';
2// Or
3import {sampleOrderedPairs} from 'pandemonium';
4
5sampleOrderedPairs(2, ['apple', 'orange', 'pear', 'pineapple']);
6>>>  [['apple', 'pear'], ['pear', 'orange']]
7
8// Alternatively, you can pass a length and get a sample of pairs of indices
9sampleOrderedPairs(2, 4);
10>>> [[0, 2], [2, 1]]
11
12// To create your own function using custom RNG
13import {createSampleOrderedPairs} from 'pandemonium/sample-ordered-pairs';
14
15const customSampleOrderedPairs = createSampleOrderedPairs(rng);

weightedReservoirSample

Function returning a random sample of size k from a given array of weighted items.

The result is a sample without replacement, which, in the case of weighted items, has been chosen to mean that subsequent items are picked based on the proportional total weight of the remaining items.

We use algorithm "A-ES" from the following papers:

Pavlos S. Efraimidis, Paul G. Spirakis. "Weighted random sampling with a reservoir." https://arxiv.org/pdf/1012.0256.pdf

Pavlos S. Efraimidis. "Weighted Random Sampling over Data Streams."

This function runs in O(n) time and O(k) memory.

A helper class working able to work on an arbitrary stream of data that does not need to fit into memory is also available if you need it.

1import weightedReservoirSample from 'pandemonium/weighted-reservoir-sample';
2// Or
3import {weightedReservoirSample} from 'pandemonium';
4
5weightedReservoirSample(2, [.1, .1, .4, .3, .05]);
6>>> [.3, .4]
7
8// To create your own function using custom RNG
9import {createWeightedReservoirSample} from 'pandemonium/weighted-reservoir-sample';
10
11const customWeightedReservoirSample = createWeightedReservoirSample(rng);
12
13// To sample arbitrary items
14const data = [{label: 'orange', importance: 34}, ...];
15
16const customWeightedReservoirSample = createWeightedReservoirSample({
17  getWeight: item => item.importance
18});
19
20// To use the helper class
21import {WeightedReservoirSampler} from 'pandemonium/weighted-reservoir-sample';
22
23// If RNG is not provided, will default to Math.random
24const sampler = new WeightedReservoirSampler(10, {rng, getWeight});
25
26for (const value of lazyIterable) {
27  sampler.process(value);
28}
29
30// To retrieve the sample once every value has been consumed
31const sample = sampler.end();

Contribution

Contributions are obviously welcome. Please be sure to lint the code & add the relevant unit tests before submitting any PR.

git clone git@github.com:Yomguithereal/pandemonium.git
cd pandemonium
npm install

# To lint the code
npm run lint

# To run the unit tests
npm test

License

MIT