# Choosing a random integer in a range such that it doesn't equal a particular number

Given an integer range and a number within that range, what's a reasonably robust and efficient way to randomly select a new number within the range such that it's not equal to the given number?

Whenever I need to do this, I usually use something like:

``````// Randomly choose an integer within an inclusive range with the condition
// that the result not equal the previous number chosen
// INPUT: lastNum is an int in the range [minVal, maxVal]
int ChooseNewNumber(lastNum){

minVal = 0;
maxVal = N; // This would usually be a value like someContainer.size - 1
intervalLength = maxVal - minVal + 1;

// Assume RandomInt...() is an existing function that lives up to its name
int newNum = RandomIntWithinInclusiveRange(minVal, maxVal);

if (newNum == lastNum){
// Add a random offset to newNum and wrap around if necessary
newNum = (newNum+RandomIntWithinInclusiveRange(1, intervalLength - 1)) % (maxVal+1);
}

return newNum;
}
``````

This works and it seems to avoid the introduction of any bias in the `newNum == lastNum` case, but it's a bit clunky. Is there a cleaner way to accomplish the same thing?

EDIT: as coredump pointed out, the method above fails if `minVal != 0`. Just for reference, the line:

``````newNum = (newNum+RandomIntWithinInclusiveRange(1, intervalLength - 1)) % (maxVal+1);
``````

should be:

``````new = ((new + RandomIntWithinInclusiveRange(1, intervalLength - 1) - minVal) % intervalLength) + minVal;
``````

I realize this mistake gave the impression that `minVal` might always be 0; sorry about that.

• Instead of generating a number between `minVal` to `maxVal`, generate one from `minVal` to `maxVal - 1`, and if the number is equal to or greater than `lastNum`, increment it by one. Granted, you don't want to do this with non-ints. Also, you'll still need to do bounds checking and perhaps adjust for negative numbers being possible. But, you'll only need to generate one number. – Lawtonfogle Dec 5 '14 at 16:30
• Do note that if the range actually stays the same and you simply want to sample without repetitions, it's usually done by creating an array of the range, shuffling it and then just popping off the next number. – TC1 Dec 5 '14 at 22:50
• You probably want your random numbers to have a uniform distribution. If this is so pick ractchet freak's answer. – Michael Le Barbier Grünewald Dec 6 '14 at 8:57
• @MichaelGrünewald And why not my answer instead ;-) ? Isn't it equally uniform? – coredump Dec 6 '14 at 12:39
• @coredump You answer is also equally uniform and fine, yet there is a small confusion between 0 and minval I guess. – Michael Le Barbier Grünewald Dec 6 '14 at 13:46

Just take a number in the range `[minVal, maxVal-1]` and add 1 if it is greater or equal to `lastNum`

``````int ChooseNewNumber(lastNum){
minVal = 0;
maxVal = N;
if(minVal > lastNum || lastNum > maxVal){
//if lastNum is outside range then just take full range
return RandomIntWithinInclusiveRange(minVal, maxVal);
}
random = RandomIntWithinInclusiveRange(minVal, maxVal-1);
if(lastNum <= random) random++;
return random;
}
``````
• Upon first reading, I thought that this might introduce some bias or other nastiness. I wanted to suggest an alternative: generate a random number between [0, size_of_range-1] and interpret that as an index into the range … but then I immediately realized that that's the same thing, so, now I am convinced that there is no bias in your method. And it's much simpler! – Jörg W Mittag Dec 5 '14 at 16:42
• Hmm. I've used the increment approach in the past, but I switched to the random offset after concluding that it doubled the odds of `lastNum+1` being chosen. Can you explain why this doesn't bias the result? Also, as specified in the question, `lastNum` will always be in `[minVal, maxVal]`, so the simple full range approach will never be used. – Reign of Error Dec 5 '14 at 16:47
• @ReignofError no because if `RandomIntWithinInclusiveRange(minVal, maxVal-1);` selects `lastNum+1` then it gets incremented to `lastNum+2`. That's why I increment the entire range between lastNum and maxVal. – ratchet freak Dec 5 '14 at 16:48
• @ReignofError Sounds like you had a `<` somewhere where you needed a `<=` or vice-versa – Ordous Dec 5 '14 at 16:50
• @ratchetfreak Ah, I see. Thanks for the explanation. – Reign of Error Dec 5 '14 at 16:54

Just choose between 1 and `N` and return 0 if the value is `lastNum`.

``````int ChooseNewNumber(lastNum){
random = RandomIntWithinInclusiveRange(1, N);
if (random == lastNum) {
return 0;
}
return random;
}
``````

Or the shorter version, if you prefer:

``````int ChooseNewNumber(lastNum){
random = RandomIntWithinInclusiveRange(1, N);
return (random == lastNum ? 0 : random);
}
``````

There was a little confusion about why I did actually wrote 0 and 1 instead of `minVal` and `maxVal`. For my defense, I found the original question equally confusing ;-) (cf. comment). Here is a modified version, with those variables given as parameters and with all assumptions explicitly checked:

``````int ChooseNewNumber(minVal, maxVal, lastNum){

assert(minVal =< lastNum);
assert(lastNum =< maxVal);
assert(minVal < maxVal); /* there is at least one value */

random = RandomIntWithinInclusiveRange(minVal, maxVal);
return (random == lastNum ? (minVal + 1) : random);
}
``````

Note however that since `lastNum` is supposed to be the last number picked, we could safely assume that it belongs to the intended interval.

Below, I still assume that `minVal` is 0 and `maxVal` is `N`, which makes sense in my example and keeps the explanation simpler.

## Explanation

Image a deck of 4 cards:

``````ABXD
``````

X is at position `lastNum`.

Then, you want to pick only A,B or D.

This is equivalent to picking a random card in this set,

``````XBAD
``````

... where you would swap `lastNum` and 0 and choose an element between 1 and `N`.

But in fact, you can do this without actually swapping elements.

• Nice simple solution. I like it. And not just because I was going to post this exact same thing had you not already done so. ;-) – Chris Dec 5 '14 at 23:18
• +1 This and ratchet freak's answers are two takes on same approach: map "N random outcomes" to "N random outcomes that exclude some value". In your case, you map lastNum to 0, and in ratchet freak's solution, he maps lastNum and up to the number +1. lastNum gets skipped either way. Either way is great because it only requires a single random generation and a single "if" – Rob Dec 6 '14 at 0:16
• @RobY This is the same idea, but I still find that mine is a little more straightforward. Look: no need to compute N-1, no range check, no increment, no inequality test. The shifting done by ratchet freak's is maybe a little too "clever" and I did find it confusing at first sight (the two first comments say how people wasn't easily convinced there is no bias). – coredump Dec 6 '14 at 3:41
• @Chris My actual first name is Chris, are you me ;-) ? – coredump Dec 6 '14 at 6:40
• @coredump: maybe... ;-) – Chris Dec 6 '14 at 13:11

You can also go for the scrabble method:

1. Generate a list of numbers from 1-N;
2. Select a random item from this list;
3. Remove this item from the list;
4. Use the modified list when you need your next number.

It is simply impossible to draw the same number twice in a row, because the number is not in the list anymore. It is similar to what happens in games like Scrabble or Rummy.

in C# code (untested):

``````//do this during the setup phase
List<int> numberRange = Enumerable.Range(0, N).ToList();
Random random = new Random(); //Or your random implementation of choice

//Do this when you need a number
int index = random.Next(numberRange.Count);
int chosenNumber = numberRange[index];
numberRange.Remove(chosenNumber);
return chosenNumber;
``````

Please note that this scales linearly in memory with N, and in time with N when generating the list. It is to be used if you need to ensure that you don't have the same item twice. If you don't want to pull the same number twice in a row (but you still want the number before the last number to be an option), you need to keep the original list and remove the last item using Except() BEFORE you generate your index.