Can Python generate a random number that excludes a set of numbers, without using recursion?

Question

I looked over Python Docs (I may have misunderstood), but I didn't see that there was a way to do this (look below) without calling a recursive function.
What I'd like to do is generate a random value which excludes values in the middle.

In other words,
Let's imagine I wanted X to be a random number that's not in
range(a - b, a + b)
Can I do this on the first pass,
or
1. Do I have to constantly generate a number,
2. Check if in range(),
3. Wash rinse ?

As for why I don't wish to write a recursive function,
1. it 'feels like' I should not have to
2. the set of numbers I'm doing this for could actually end up being quite large, and
... I hear stack overflows are bad, and I might just be being overly cautious in doing this.

I'm sure that there's a nice, Pythonic, non-recursive way to do it.

Answer 1

Generate one random number and map it onto your desired ranges of numbers.

If you wanted to generate an integer between 1-4 or 7-10, excluding 5 and 6, you might:

1. Generate a random integer in the range 1-8
2. If the random number is greater than 4, add 2 to the result.

The mapping becomes:

Random number:    1  2  3  4  5  6  7  8
Result:           1  2  3  4  7  8  9 10

Doing it this way, you never need to "re-roll". The above example is for integers, but it can also be applied to floats.

Answer 2

Use random.choice(). In this example, a is your lower bound, the range between b and c is skipped and d is your upper bound.

import random
numbers = range(a,b) + range(c,d)
r = random.choice(numbers)

Answer 3

A possible solution would be to just shift the random numbers out of that range. E.g.

def NormalWORange(a, b, sigma):
    r = random.normalvariate(a,sigma)
    if r < a:
        return r-b
    else:
        return r+b

That would generate a normal distribution with a hole in the range (a-b,a+b).

Edit: If you want integers then you will need a little bit more work. If you want integers that are in the range [c,a-b] or [a+b,d] then the following should do the trick.

def RangeWORange(a, b, c, d):
    r = random.randrange(c,d-2*b) # 2*b because two intervals of length b to exclude
    if r >= a-b:
        return r+2*b
    else:
        return r

Answer 4

I may have misunderstood your problem, but you can implement this without recursion

def rand(exclude):
    r = None
    while r in exclude or r is None:
         r = random.randrange(1,10)
    return r

rand([1,3,9])

though, you're still looping over results until you find new ones.

Answer 5

The fastest solution would be this (with a and b defining the exclusion zone and c and d the set of good answers including the exclusion zone):

offset = b - a
maximum = d - offset
result = random.randrange(c, maximum)
if result >= a:
    result += offset

Answer 6

You still need some range, i.e., a min-max possible value excluding your middle values.

Why don't you first randomly pick which "half" of the range you want, then pick a random number in that range? E.g.:

def rand_not_in_range(a,b):
    rangechoices = ((0,a-b-1),(a+b+1, 10000000))
    # Pick a half
    fromrange = random.choice(rangechoices)
    # return int from that range
    return random.randint(*fromrange)

Answer 7

Li-aung Yip's answer makes the recursion issue moot, but I have to point out that it's possible to do any degree of recursion without worrying about the stack. It's called "tail recursion". Python doesn't support tail recursion directly, because GvR thinks it's uncool:

http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

But you can get around this:

http://paulbutler.org/archives/tail-recursion-in-python/

I find it interesting that stick thinks that recursion "feels wrong". In extremely function-oriented languages, such as Scheme, recursion is unavoidable. It allows you to do iteration without creating state variables, which the functional programming paradigm rigorously avoids.

http://www.pling.org.uk/cs/pop.html