# Generate random numbers from an interval with holes

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].

• I approached it this way - 1. Generate random numbers between [0,N) 2. If the number belongs to S.. map it uniformly to N-k numbers.. So suppose, S= {4, 6, 9} and N=10 Lets say the first random num generated is 6. Map 6 to 0. Next time when 6 is generated map it to 1.. and so on till 9.. Then repeat this again – abipc Jul 14 '13 at 14:13
• So on an average, the probability of generating any of the N-k number is equal..(statistically) – abipc Jul 14 '13 at 14:15
• What do you want to achieve (efficiency? minimal number of coins flipped?)? why not just picking a uniform number in $[0, N-|S|)$ with a trivial mapping to $\overline S$? – Ran G. Jul 14 '13 at 20:06
• Hey, don't feel stupid.. just clarify your requirements, otherwise the question trivializes: you generate a number in $[0,N)$, if it is in $S$ you repeat. Now, this might run for a long time, but will work... – Ran G. Jul 16 '13 at 0:25
• @RanG.Yep..That one i knew (repeat if you get an element in S) .. Thanks for coming back.. – abipc Jul 16 '13 at 12:19

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

• @Pratik..+1 for some concepts that i was able to recall coz of ur answer and the link in it.. But I am not able to use your solution.. may be i m doing something wrong.. am attaching what i m doing.. – abipc Jul 15 '13 at 6:45
• PMF(in Java): double[] A = {(double)1/7, (double)1/7, (double)1/7 ,(double)1/7, 0, (double)1/7, 0, (double)1/7, (double)1/7, 0}; When i use ur solution i dont get the expected result..Can u correct me? – abipc Jul 15 '13 at 7:01
• What result do you get? Can you try and roll the die for 1000 times and observer the frequency of each number? – Pratik Deoghare Jul 15 '13 at 7:07
• I am getting numbers from Set S as well.. My PMF is right?? – abipc Jul 15 '13 at 7:09
• I think the problem is because of floating point numbers. Or maybe becau\se result = 1 earlier. I have changed the code so that you don't have to use floating point numbers and result = 0. – Pratik Deoghare Jul 15 '13 at 19:42

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.