Generating random number excluding range

Question

How do you generate a random number within a range while excluding certain range(s). Eg. range 1-10 but not in 2-4 or 7. Solutions I've used so far:

• Generate a random an test if it is within the dis-allowed range. Based on result either output the number or try again.
• Map allowed ranges to a uniform range. Get a random between 1 and 6 and then map back (ie. 6 becomes 10).
• Create allowed ranges (1-1,5-6,8-10). Randomly choose a range (optionally use weights) and a number in chosen range.

What is your solution?

Answer 1

Map them to the total of the ranges you expect. then distribute them between the ranges.

E.g. if you need a random between 0..10 and 100..110

Generate a random-number between 20. The lower 10 get assigned to the 0..10 range, the rest to the other interval (or something like that - I may be off by one.. Interval arithmetic is one of these things that I never get right on the first try).

The reason behind this is that you often deal with non perfect random generators. These start to behave strange if you distribute successive random-number variables over several dimensions (e.g. first choose a random interval, then choose a random inside the chosen interval). That can lead to a very obvious non-random behavior.

If you start with a better random number generator that gets it's data from true random sources you may end up wasting precious random bits. If you do it just once every second it may not be a problem. If you do it to often though you program might get stalled because the pure random sources have to catch up with your random-bit consume.

Answer 2

(b) Use the single range and map to allowed values.

(a) Is slower and running time is non-deterministic because you have to wait until you get a number in the right range. If you were to skip a large range, you'd be hosed.

(c) Is more complex than (b); don't add complexity if it isn't required.

Answer 3

It would depend on how many/big the exclusion ranges are. Testing for dis-allowed range (your option 1) would work fine for small sets; no need to complicate the solution to an easy problem. Solution 3 would work better for more numerous exclusion sets. Solution 2 is the most work, but probably the most correct theoretical solution.

Answer 4

It sounds like your algorithm can benefit from a slight redesign that will make creating the random numbers implicit rather than explicitly finding them using a random number generator.

For instance if you want to get a random series of the numbers from 1 to 10, its better to start from an ordered series, mix it in some fashion for instance via swapping (there was a question about this I think) and take the numbers one after the other.

Answer 5

I generally use the technique described by bullet number two above, especially if the set of allowable numbers is reasonably small. From a statistical standpoint, it's way to easy to either ruin the randomness of the results or skew the results away from a flat distribution.

It has the added advantage of allowing a single pick (like dealing cards or picking bingo balls) ... you simply remove the already selected values from the map.