Prevent repetitive random numbers

Question

Is this a good way to prevent two sequential numbers from repeating, or is there a better, more efficient way of doing this? By efficient, I mean a less CPU and memory consuming process.

while (random === lastrandom) {
    random = Math.floor(Math.random() * 3) + 1;
}
lastrandom = random;

Answer 1

In practice, your code will be fine. In theory, it is not guaranteed to terminate, but the probability of that happening is literally negligible.

However, what you are doing is picking a random integer between 1 and 3 (both inclusive), with the number not repeating. With only three possibilities, we could draw up a state machine:

states = {
  1: [2, 3],
  2: [1, 3],
  3: [1, 2] };
if (lastRandom === undefined) {
    random = Math.floor(Math.random() * 3) + 1;
}
else {
    random = states[lastRandom][Math.floor(Math.random() * 2)];
}
lastRandom = random;

Unfortunately, that involves generating all the states first, which is impractical for larger ranges. There, we could use this more clever approach:

var min = 1;
var max = 3;
if (lastRandom === undefined) {
    random = Math.floor(Math.random() * (max - min + 1)) + min;
}
else {
    random = Math.floor(Math.random() * (max - min    )) + min;
    if (random >= lastRandom) random += 1;
}
lastRandom = random;

So if we are choosing the first number, everything works as usual. But for any subsequent number, we choose an integer from a set one smaller (to reflect that one number, the lastRandom, can't be chosen). If the random number obtained like this is less than the lastRandom, it can be used as is. Otherwise it has to be incremented by one, so that the lastRandom has been skipped.

Test to compare code:

Answer 2

You can do this without checking what the previous selection was. On the first iteration, you select a number from 1 to n, call this r. However, subsequent iterations should select a number from 1 to (n - 1), call this rn. The next random number in the sequence is then ((r-1 + nr) % n) + 1

It works like this: imagine the numbers 1:n are stored in array. If you start at some position x, you get to the next position x, but not back to x, by adding n-1 to x (but not going past the nth index by starting over at the beginning when you pass it, hence the modulus operation). That's kind of hard to visualize without a diagram and i'm not good at making internet forum diagrams.

Answer 3

Your code only allows you to prevent repeating any two consecutively-generated numbers, it does not prevent collisions with numbers that have been generated on previous iterations - to do that, you would need to keep an array of all the previously generated values and iterate through them.

Answer 4

This is my solution and suggestion to the problem.

function random(min, max, length) {    
    var numbers = [];

    function _random(min, max) {
        return Math.floor(Math.random() * (max - min + 1)) + min;
    }

    Array.apply(null, new Array(length)).reduce(function(previous) {
        var nextRandom;

        if(previous === min) {
            nextRandom = _random(min + 1, max);
        } else if(previous === max) {
            nextRandom = _random(min, max - 1);
        } else {
            if(_random(0, 1)) {
                nextRandom = _random(previous + 1, max);                
            } else {
                nextRandom = _random(min, previous - 1);            
            }
        }

        numbers.push(nextRandom);
        return nextRandom;
    }, _random(min, max));

    return numbers;
}

And here is a JSBin containing some tests. Also I would like some feedback!

Answer 5

Fun question,

I really like Amon's answer and wanted to add one more variation to his approach.

My approach would encapsulate the code into a function with 1 re-usable state.

function Generator( n ){
  //Build full array with all possibilities
  var numbers = [], temp = n;
  while (temp--)
    numbers[temp] = temp+1;
  //Remember 1 randomly removed number 
  var index = Math.floor(Math.random() * n--),
      last  = numbers.splice(index, 1)[0];

  function generate(){
    //Choose a remaining number, swap out it for the last random number
    index = Math.floor(Math.random() * n);
    temp = last;
    last = numbers[index];
    numbers[index] = temp;
    return last;
  }
  return generate;
}

You can find a jsbin here: http://jsbin.com/sizigo/1/edit

Of course, for anything besides a hobby project I would go with your approach except that I would write my own RNG.

Answer 6

Given that you only want to avoid the most recent result, what you're essentially asking for is "a random number between A and B that is not C". This can be pretty easily achieved by generating a random number between A and (B - 1), then, if you got C, returning B.

In code:

var random = MIN + Math.random() * (MAX - (lastRandom !== undefined)) | 0;
if (random === lastRandom) random = MAX;
lastRandom = random;

Instead of - 1 I have - (lastRandom !== undefined) so that, before lastRandom is set, you select over the full range.

(Side note: | 0 does the same thing as Math.floor, but faster and more concisely. Though counterintuitive at first, I tend to think it's worth getting used to.)