How can I generate a random number within a range but exclude some?

Question

How can I generate a random number within a range but exclude some, without keep generating and checking if the generated number is one of those that I want to exclude?

Answer 1

One possible solution without regeneration the random each time is to use the following algorithm:

public int getRandomWithExclusion(Random rnd, int start, int end, int... exclude) {     int random = start + rnd.nextInt(end - start + 1 - exclude.length);     for (int ex : exclude) {         if (random < ex) {             break;         }         random++;     }     return random; } 

This method can be either called with an array reference, e.g.

int[] ex = { 2, 5, 6 }; val = getRandomWithExclusion(rnd, 1, 10, ex) 

or by directly inserting the numbers into the call:

val = getRandomWithExclusion(rnd, 1, 10, 2, 5, 6) 

It generates a random number (int) between start and end (both inclusive) and does not give you any number which is contained in the array exclude. All other numbers occur with equal probability. Note, that the following constrains must hold: exclude is sorted ascendingly and all numbers are within the range provided and all of them are mutually different.

Answer 2

/**  * @param start start of range (inclusive)  * @param end end of range (exclusive)  * @param excludes numbers to exclude (= numbers you do not want)  * @return the random number within start-end but not one of excludes  */ public static int nextIntInRangeButExclude(int start, int end, int... excludes){     int rangeLength = end - start - excludes.length;     int randomInt = RANDOM.nextInt(rangeLength) + start;      for(int i = 0; i < excludes.length; i++) {         if(excludes[i] > randomInt) {             return randomInt;         }          randomInt++;     }      return randomInt; } 

The idea is to reduce the range wherein the random number is generated to the difference between start and end minus count of numbers within that range that are excluded.

So you get a range length which is identical with the count of possible valid numbers. In other words: You've removed all holes from range.

After generating the random number you've to put the "holes" back in the range. This can be achieved by incrementing the generated number as long as there are excluded numbers lower than or equal to the generated one. The lower exclude numbers are "holes" in the range before the generated number. And the generated number is shifted to right for every hole before that number.