# Uniformly generate a number from 0 to n-1 that isn't on a blacklist

Given an integer n and a list of integers l, write a function that randomly generates a number from 0 to n-1 that isn't in l (uniform).

Solution 1:

const getRandNotInList = (n , list) => {
const rand = Math.floor(Math.random() * n);
return list.includes(rand) ? getRandNotInList(n, list) : rand;
};

console.log(getRandNotInList(16, [1,2,3,4]));


Solution 2:

const getRandNotInList2 = (n, list) => {
let rand;
do { rand = Math.floor(Math.random() * n); }
while(list.includes(rand));
return rand;
};

console.log(getRandNotInList2(13, [2,3,4,5,6]));

• what does l (uniform) mean? quick google search gave me list of school uniforms. Commented Feb 13, 2019 at 18:23
• Probably uniform random numbers: de.mathworks.com/help/simulink/slref/uniformrandomnumber.html Commented Feb 13, 2019 at 18:43
• yeah that makes sense. I thought it was the list that was uniform. Commented Feb 13, 2019 at 18:43

The problem is backwards. You would never present a exclusion list for random values, rather you would present a list to randomly pick from.

Anyways to fit the problem.

# Two ways this can be done

1. Guessing
2. Deterministically

## Guessing

Your method use a random guess, you guess that the number is not in the list. If it is you guess again. This works well when the list contains only a small set of the numbers.

However when the exclusion list gets larger you need to make more guess to find one that is not in the list. The number of guess grows very fast as your exclusion list gets closer to excluding all.

This is the worst possible performance at $$\O(m^{-(1/n)})\$$ it has an Infinity

The other problem with guessing is that you can not know how long the function is going to run for. This makes it totally unsuitable for many real time applications.

## Deterministically

You can improve the overall performance and have a function that has a known fixed time to get a result.

However is is much slower when the exclusion list is relatively small.

The performance is linear at $$\O(n)\$$

If the exclusion set does not change between calls it get even less complex at $$\O(1)\$$ which is the best you can get.

## Example

The $$\O(n)\$$ solution

It returns undefined if it can not find a number rather than throw. You should not be solving the calling function problems as the other answers suggest.

const getRandNotInList = (n, list) => {
const picks = [];
const getPickable = () => {
var i = 0; dir = Math.sign(n);
list = new Set(list);
while (i !== n) {
!list.has(i) && picks.push(i);
i += dir;
}
}
n = Math.floor(n);
if (n === 0) { return list.includes(0) ? undefined : 0 }
getPickable();
return picks[Math.random() * picks.length | 0]; // (| 0) same as Math.floor
// (only for positive ints).
}

• Why do not you just use if (!list.has(i)) but rather !list.has(i) &&? (Or even better rename the variable as set = new Set(list); so a list does not represent a Set? Commented Aug 18, 2019 at 22:33
• @KorayTugay I find minimal evaluation more concise for single line statements that are not suited to ternaries. Why create a second variable, that would mean two references to the same data, one as an array and again as a set. However i did use the wrong type of set and should have used a WeakSet Commented Aug 19, 2019 at 5:57

As already mentioned, most JS engines don't do TCO so your recursive approach may stack overflow. Often, functional programming in Javascript means using the functional utilities like map and reduce with closures.

So, your second solution is preferable in this regard. Although, I'd clean it up a little to be a regular function definition instead of needlessly using fancy ES6 syntax:

function getRandNotIn(below, excluding) {
// ...
}


One thing to consider, though, is the performance characteristics of doing while (excluding.includes(num)). If you are only excluding a few numbers, it won't be too expensive (and won't be run many times because on average choosing an excluded number will be rare). But, as excluding.length approaches below the statistical expectation is that there will be more collisions, which means more O(n) traversals. You're probably better off using a Set here. Doing so would then allow you to assert:

if (excluding.length >= below) throw "can't exclude all numbers";


If excluding wasn't a set, then this assertion would be incorrect because a number could be duplicated. You also probably want to assert this for only numbers in 0 <= num < below (as numbers outside that range don't count):

if ((new Set(excluding.values.filter(n => 0 <= n && n < below))).length >= below) throw "...";


When you run Solution 1 with the following parameters:

getRandNotInList(4, [0,1,2,3])


you quickly get an error, at least in Google Chrome.

Uncaught RangeError: Maximum call stack size exceeded

This is because JavaScript engines typically don't implement tail recursion.

Therefore I prefer Solution 2 over Solution 1, which just leads to an endless loop.

(Note to myself: Don't try endless loops in the browser. Google Chrome will just freeze completely.)

Therefore a proper solution should not end in an endless loop. Just check whether list.length >= n and throw an exception in such a case. If the list should ever contain duplicates that's the problem of the caller.

const getRandNotInList3 = (n, list) => {
if (list.length >= n) throw "blacklist must not forbid all possible elements";
let rand;
do { rand = Math.floor(Math.random() * n); }
while(list.includes(rand));
return rand;
};

• How do you know if the list length is greater than n that it contains any values between 0 and n, Eg getRandNotInList(2, [5,6,7]) would incorrectly throw! Commented Feb 14, 2019 at 1:12
• @Blindman67 Thanks for finding this. I had only thought about duplicate values in the list. Commented Feb 14, 2019 at 13:31