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

Question

The task:

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]));

Answer 1

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).
}

Answer 2

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 "...";

Answer 3

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;
};