Implement "exhaustive" option

[Bellisario]

Closes #9.

P.S.: I focused on coding instead of adding an example on readme or new example on types... if I need provide some code examples, let me know!

[sindresorhus]

You will need to document it in the readme too.

Use this style: https://github.com/sindresorhus/boxen#options

[sindresorhus]

I think the option needs a better name. It does actually allow repetition, just not until all the numbers have been used up.

[Bellisario]

I just updated with requested changes, let me know if there is something to correct. I also changed the name from preventRepeat to option noOverlap, tell me if this is a good way to call it... Now I'll focus on README.md updates... :smiley:

[Richienb]

The original code called random() if the previous value matched the current one.

Where $n$ is the range of possible numbers, we can calculate how many times on average random is actually being called each time the consumer calls it, excluding the first call which doesn't have a previous value:

$$ c = \frac{1}{\frac{n - 1}{n}} $$

where $\frac{n - 1}{n}$ calculates the chance of generating the number first try and we find the reciprocal to discover the amount of times we take that chance for it to theoretically be 100%.

For a range of 5 numbers, $c = 1.25$. This means each time random is called, it is actually called 1.25 times because of the recursion.

This amount decreases with the amount of numbers since there is a lower chance of collision. This means for $n = 50$, $c \approx 1.02$

The new algorithm has the inverse effect since this time, there are multiple previous numbers, increasing the chance of collision. To iterate over a set of 5 numbers, 5 calls to random() is optimal. However, because of the recursion, we can calculate the actual amount with:

$$ t = \sum_{i=1}^{n} \frac{1}{\frac{i}{n}} $$

where $n$ is the range of numbers we are generating. For $n = 5$, $t \approx 11.42$ and for $n = 50$, $t \approx 224.96$.

Here, we graph $x$ as the range of numbers and $y$ as the amount of calls required:

As you can see, the recursion is catastrophic. The tests only check for a range of 1000 numbers, where $t \approx 7485.47$ which isn't large enough for the lag to be easily noticable so it hasn't been discovered experimentally.

I believe the most straightforward solution would be the Tetris sack system, whereby the numbers are generated beforehand with a shuffle and then pulled out of the "sack" one by one until empty.

[Bellisario]

@Richienb, @sindresorhus, I updated the algorithm using the sack system to improve performance. Now should be about comparable to the original random extraction, with the only limit of the initial Set configuration (for-loop) with all values can be extracted.

[sindresorhus]

I don't think noOverlap is a good enough option name.

[Bellisario]

I don't think noOverlap is a good enough option name.

I don't know how we could name this option... :tired_face: seems very difficult to me, because it's particular...

[Richienb]

exhaustRange?

exhaustiveSequence?

[Bellisario]

Maybe also just sack, because of the sack system. (simpler, single word, and not a negation)...

[sindresorhus]

Maybe also just sack, because of the sack system. (simpler, single word, and not a negation)...

I don't think most users of this package would know what "sack" is.

[sindresorhus]

I don't know how we could name this option...

A big part of submitting a pull request is docs and naming. Try to do some research ;)

[Bellisario]

I found the technical name of this "sack system": Shuffle Bag. Here is for example a C# article talking about it: https://gamedevelopment.tutsplus.com/tutorials/shuffle-bags-making-random-feel-more-random--gamedev-1249

The problem is that also this name is not so simple to remember, to use, intuitive and a simple English word, so I think the best solution is to call it bag, which is a common English word and in this case self-explains the use.

P.S.: I noticed that the Node.js 12 CI was not able to test, this is because optional chaining used here is supported only on Node.js 14 and above, so I fixed by checking options object existence and force an empty object if none passed.

[sindresorhus]

bag is the same as sack. A technical term that is meaningless with more context.

[sindresorhus]

Let's go with exhaustive for now and instead include great explanatory docs.

[sindresorhus]

There's one more constraint we need to enforce with this option, we need to make sure that the last number in the first round is not the same as the first number in the second round.

We don't want repeat numbers on the boundaries, for example:

import uniqueRandom from 'unique-random';

const random = uniqueRandom(1, 3, {exhaustive: true});

console.log(random(), random(), random(), random(), random(), random());
//=> 3
//=> 1
//=> 2
//=> 2
//=> 3
//=> 1

The 2 and 2.

This also needs a test.

[Bellisario]

There's one more constraint we need to enforce with this option, we need to make sure that the last number in the first round is not the same as the first number in the second round.

We don't want repeat numbers on the boundaries, for example:

import uniqueRandom from 'unique-random';

const random = uniqueRandom(1, 3, {exhaustive: true});

console.log(random(), random(), random(), random(), random(), random());
//=> 3
//=> 1
//=> 2
//=> 2
//=> 3
//=> 1

The 2 and 2.

This also needs a test.

This should already be enforced with:

https://github.com/Bellisario/unique-random/blob/0c9ae5d1a0d45ee7de282aa8a91de87fe4f98333/index.js#L21-L23

and tested with:

https://github.com/Bellisario/unique-random/blob/0c9ae5d1a0d45ee7de282aa8a91de87fe4f98333/test.js#L44

Is there any issue?\ Maybe I missed something and tests can't identify...

[sindresorhus]

Bump