3

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.

  • 2
    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
  • 1
    @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
15

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
  • 3
    @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
6

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);
}

The generic answer (EDIT)

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.

  • 1
    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
    +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
  • 1
    @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
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.