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
