In python, how to generate a random integer in a range, excluding some numbers in a list?

Question

For example, at beginning I want generate a random integer from (0,9),

at first time, the program generate 2, then I put 2 in the 'excluding' list,

next time, I need generate a number ranging between 0 to 9, and excluding 2. let's say it the second turn, the program generate 5.

The third turn, I need generate a number ranging from 0 to 9 and excluding 2 and 5.

As the range is very huge (million level), is there any method is efficient?

Answer 1

Generate the possible values once, shuffle that and pop values from that list each time:

values = range(10)
random.shuffle(values)

def get_value():
    return values.pop()

This will eventually produce all values in the range, in random order, without repetition.

Answer 2

As per the documentation for random.sample:

To choose a sample from a range of integers, use an xrange() object as an argument. This is especially fast and space efficient for sampling from a large population: sample(xrange(10000000), 60).

This will sample without replacement, so random.sample(xrange(n), k) gives k different numbers in the range [0, n) (for k <= n).