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

  • $\begingroup$ 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 $\endgroup$
    – abipc
    Commented Jul 14, 2013 at 14:13
  • $\begingroup$ So on an average, the probability of generating any of the N-k number is equal..(statistically) $\endgroup$
    – abipc
    Commented Jul 14, 2013 at 14:15
  • 4
    $\begingroup$ 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$? $\endgroup$
    – Ran G.
    Commented Jul 14, 2013 at 20:06
  • 2
    $\begingroup$ 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... $\endgroup$
    – Ran G.
    Commented Jul 16, 2013 at 0:25
  • $\begingroup$ @RanG.Yep..That one i knew (repeat if you get an element in S) .. Thanks for coming back.. $\endgroup$
    – abipc
    Commented Jul 16, 2013 at 12:19

2 Answers 2

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

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
  • $\begingroup$ @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.. $\endgroup$
    – abipc
    Commented Jul 15, 2013 at 6:45
  • $\begingroup$ 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? $\endgroup$
    – abipc
    Commented Jul 15, 2013 at 7:01
  • $\begingroup$ What result do you get? Can you try and roll the die for 1000 times and observer the frequency of each number? $\endgroup$ Commented Jul 15, 2013 at 7:07
  • $\begingroup$ I am getting numbers from Set S as well.. My PMF is right?? $\endgroup$
    – abipc
    Commented Jul 15, 2013 at 7:09
  • $\begingroup$ 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. $\endgroup$ Commented Jul 15, 2013 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.