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

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?

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.

/**
 * @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.

The best aproach that you can follow to randomize numbers, excluding some is selecting the numbers that you want first and then randomly select the numbers selected. For example, in pseudocode:

List<Number> numbers;

numbers.add(1);
numbers.add(2);
numbers.add(3);
//You can do a "for" without adding the excluded numbers..

//Then, your randomizer could be...

public Number getRandoNumber() {
    int index = Random.get(0, numbers.size());
    return numbers.get(index);
}

Now, you don't need to check if the "generated number" is allowed or not, because it doesn't exist at all.

If you don´t want them to repeat, you can do something like:

Collections.shuffle(numbers);

public Number getRandomNotRepeat() {
     if(numbers.size() == 0)
        throw new RuntimeException("No more numbers");

       Number n = numbers.get(0);
       numbers.removeFirst();

       return n;
}

This is all pseudo code, don´t copy and paste!

I think the additional question is: What are the numbers you want to exlcude? Do they represent some sort of range or are they totally random?

If it was a range of numbers you want to ignore, you could generate your random numbers from within few sets that represent only valid numbers:

rand(1,9);
rand(15,19);
rand(22,26);

this way you are sure you will never select excluded: <0,10,11,12,13,14,20,21,>27

Then, when you get your 3 numbers, you could again randomly select one of them.

If excluded numbers are all over the place than I'm afraid you'd have to check it every time against some sort of collection of excluded numbers.

Create a map that takes the output of a random function without the range restriction and map it to the range you want with restrictions.

For example, if I want a random int from 1-10 but never 7 I could do something like this:

int i = rand(1, 9);
if i>=7
  i++;
return i;

As long as you ensure that your mapping is 1:1, you can avoid skewing the randomness of your rand function.

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

Related

Recent Posts