1
$\begingroup$

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

$\endgroup$
  • $\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 Jul 14 '13 at 14:13
  • $\begingroup$ So on an average, the probability of generating any of the N-k number is equal..(statistically) $\endgroup$ – abipc Jul 14 '13 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. Jul 14 '13 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. Jul 16 '13 at 0:25
  • $\begingroup$ @RanG.Yep..That one i knew (repeat if you get an element in S) .. Thanks for coming back.. $\endgroup$ – abipc Jul 16 '13 at 12:19
1
$\begingroup$
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
$\endgroup$
  • $\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 Jul 15 '13 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 Jul 15 '13 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$ – Pratik Deoghare Jul 15 '13 at 7:07
  • $\begingroup$ I am getting numbers from Set S as well.. My PMF is right?? $\endgroup$ – abipc Jul 15 '13 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$ – Pratik Deoghare Jul 15 '13 at 19:42
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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