[Solved]: Generate random numbers from an interval with holes

Problem Detail: 

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

Asked By : abipc

Answered By : Pratik Deoghare

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 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13271