Generate a random integer from 0 to N-1 that is not in the list

Question

You are provided with Nand int K[].

The task is to create an equal probabilistic random number between 0 to N-1that does not exist in K.

Nis strictly an integer >= 0. And K.lengthN-1. And 0 <= K[i] <= N-1. Also suppose that K is sorted and each element of K is unique.

You are given a function uniformRand(int M)that generates a uniform random number in a range 0 to M-1. And suppose that this complexity of functions is O (1).

Example:

N = 7

K = {0, 1, 5}

the function must return any random number {2, 3, 4, 6} with equal probability.

I could get an O (N) solution for this: first create a random number from 0 to N - K.length. And compare the random number thus obtained with a number that is not in K. The second step will take complexity for O (N). Could it be better, maybe O (log N)?

Answer 1

You can use the fact that all numbers in K [] are between 0 and N-1, and they are different .

In your example, you generate a random number from 0 to 3. Say you get a random number r. Now you perform a binary search on the K [] array.

Initialize i = K.length/2.

To find K[i] - i. This will give you the number of numbers not in the array in the range of 0 to i.

For example K[2] = 5. So 3 elements are missing from K[0] to K[2] (2,3,4)

, , K . , r.

log(K.length)

EDIT: ,

N = 7

K = {0, 1, 4} // modified the array to clarify the algorithm steps.

the function should return any random number { 2, 3, 5, 6 } with equal probability.

• , 0 N-K.length= random{0-3}. , 3. , K.

• K[].

  • Initial i = K.length/2 = 1.

• K[1] - 1 = 0. , i = 1 . .

• i = 2. K[2] - 2 = 4 - 2 = 2. , 2 i = 2. 4- . .

• . ? say K[j] & K[j+1], , K[j] K[j+1] K.

• , K[2] , 5 6. 4th element, 2 elements. , , 6.

Answer 2

.

:

( , - )

• K.

• , ( K) .

  , N, .

• , .

• , .

• , .

O(log |K|), |K| < N-1, O(log N).

.

K, :

( ) K N .

, , K, min(N, |K|) .

, N - K ( ) >= N, , .

N ( , < N, N ) ( 't K, , N).

, , , < N.

O(log N) , , O(log min(N, |K|)).

:

N = 10
K = {0, 1, 4, 5, 8}

, - 4.

, 2, , 2 , 4, 4 - 2 = 2 .

, 10 - (4+1) - 2 = 3 .

, 2/(2+3) 3/(2+3).

, , - 5.

, 4, 5 - (4+1) = 0 .

10 - (5+1) - 1 = 3 .

(0 ). , 8.

2 , 1 - .

, .

, 5 8, 6 7.

Answer 3

, :

rth , K, , .

,

D[i] = K[i] - i for 0 <= i < L, where L is length of K

D[-1] = 0 D[L] = N

K[-1] = 0.

: D. , D ( ), K[] .

:

. r- , K [], r ' D ( , j), r' D, < . r ', D [-1] = 0. r' ( j), , , r-r '+ K [j].

. , r' and j , 0 to K[j] r' r , 0 to K[j+1]. , K[j]+1 to K[j+1]-1 ( r-r' ), , , , K[j] + r-r'.

:

(r',j) , , () r D, , r.

O (log K).

Answer 4

, , : O(log N) .

G. , , K. K, G. K, K. ( K.)

G, .

Use the random number generator to select a value from G.

This requires O(N)preparatory work, and each generation occurs in O(1)time. After Nsearching, the depreciation time of all operations O(1).

Python layout:

import random

class PRNG:
    def __init__(self, K,N):
        self.G = []
        kptr   = 0
        for i in range(N):
            if kptr<len(K) and K[kptr]==i:
                kptr+=1
            else:
                self.G.append(i)
    def getRand(self):
        rn = random.randint(0,len(self.G)-1)
        return self.G[rn]

prng=PRNG( [0,1,5], 7)
for i in range(20):
    print prng.getRand()