Generate random numbers from an interval with holes
-
16-10-2019 - |
Pergunta
Given a set $S$ of $k$ numbers in $[0, N)$. The task is to randomly generate numbers in the range $[0, N)$ such that none belongs to $S$.
Edit - Also given an API to generate random numbers between $[0, N)$. We have to use it to randomly generate numbers in the range $[0, N)$ such that none belongs to $S$.
I would also like a generic strategy for such questions. Another one I came across was to generate random numbers between [0,7] given a random number generator that generates numbers in range [0, 5].
Solução
0 1 2 3 4 5 6 7 8 9
0 1 2 3 - 5 - 7 8 -
"-" are in $S = \{4,6,9\}$
You can create mass distribution with $$\text{Prob}(x) = \begin{cases}\frac{1}{N - |S|} & \text{if } x \notin S\\ 0 & \text{if} \ x \in S \end{cases} $$
and then use this algorithm. Copied from here.
from collections import defaultdict
import random
def roll(massDist):
randRoll = random.random() * sum(massDist) # in [0,1)
s = 0
result = 0
for mass in massDist:
s += mass
if randRoll < s:
return result
result+=1
sampleMassDist = [1,1,1,1,0,1,0,1,1,0]
d = defaultdict(int)
for i in range(1000):
d[roll(sampleMassDist)] += 1
print d
Outras dicas
If $k$ is small (and smaller than $N$) you can generate a number $t$ in $[0,N)$ and test that it is not in $S$ before returning it. If $t$ is in $S$ (bad luck), you retry until you eventually succeeds. This is very simple and will do in many practical situations where $k$ is small and where is it easy to test for membership in $S$.
Another approach is to pick a number $t$ in $[0,N-k)$ and then compute and return the $t$-th number in $[0,N)\setminus S$. This is good when $S$ has a form simple or regular enough (e.g., the powers of 3) and it is easy to compute how many elements in $S$ are below some value. It is good also when $N$ is not too large, say $N\sim 100$, and you can precompute the $t$-th numbers.