10
\$\begingroup\$

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;
\$\endgroup\$
  • 2
    \$\begingroup\$ While not being a complete duplicate, if you only want one random number. You might want to to see this \$\endgroup\$ – Bruno Costa Sep 5 '14 at 10:18
  • 1
    \$\begingroup\$ "prevent repeating numbers" is a little ambiguous. Do you only want to avoid two repeating numbers in a row? \$\endgroup\$ – Simon Forsberg Sep 5 '14 at 11:00
  • \$\begingroup\$ @SimonAndréForsberg Yes, Simen, that's exactly what I mean - only two numbers in a row. \$\endgroup\$ – superlaks Sep 5 '14 at 11:07
  • \$\begingroup\$ By not allowing two successive random numbers to be the same, you are in essence making them a tiny bit less random... \$\endgroup\$ – Floris Sep 6 '14 at 5:31
  • \$\begingroup\$ @Floris I know that it would not be completely. However, this code is for a game I am making; this is why I need it to be non-repetitive. \$\endgroup\$ – superlaks Sep 6 '14 at 13:44
10
\$\begingroup\$

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: test on jsperf

\$\endgroup\$
  • 1
    \$\begingroup\$ Nitpick, it is guaranteed to terminate (assuming the Math.random function behaves as it should, which it probably doesn't anyway), it just might take an arbitrary (finite) amount of time to terminate, which is not the same thing! But in practice, of course, it will almost always terminate after one iteration. \$\endgroup\$ – Thomas Sep 5 '14 at 14:43
  • \$\begingroup\$ @Thomas At any call to Math.random, $1/n$ (where $n$ is the count of possible numbers) is the probability that the same number as before will be generated, causing the loop to repeat. So for any number of repetitions $x$, the probability for the loop not having terminated is $(1/n)^x$, which converges to zero but never reaches it. There is no finite number $x$ so that $(1/n)^x = 0$. This of course assumes that Math.random is a perfect RNG. Could you elaborate your (very welcome) nitpick to show me where my statistics skills failed me? \$\endgroup\$ – amon Sep 5 '14 at 20:50
  • \$\begingroup\$ It converges to zero, which essentially says that the probability of repeatedly selecting the same number and thus failing to terminate is zero. This is really what it means for the limit to converge. If you are still confused I think it would make an excellent Math.SE question. \$\endgroup\$ – Thomas Sep 5 '14 at 23:45
  • \$\begingroup\$ @amon Will this code execute faster, especially because it does not have any loops? \$\endgroup\$ – superlaks Sep 6 '14 at 18:40
  • \$\begingroup\$ @JasonStackhouse Your code can go into a loop, while my code is guaranteed to run in constant time. I therefore assume that my code will on average be faster. \$\endgroup\$ – amon Sep 6 '14 at 19:31
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Or use a kind of Set data-structure for O(1) lookup time. \$\endgroup\$ – Simon Forsberg Sep 5 '14 at 10:58
  • 2
    \$\begingroup\$ That is true, although that is not my goal. I just want to prevent two numbers after eachother, for example: 1-1, 2-2 and 3-3. \$\endgroup\$ – superlaks Sep 5 '14 at 11:00
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Although your code is good, it seems to be a little over board when there's only three possible combinations. \$\endgroup\$ – superlaks Sep 6 '14 at 13:45
  • \$\begingroup\$ @Jason Stackhouse I agree with you. For his specific case the accepted answer is best. This algorithm covers a scenario where you need a larger range \$\endgroup\$ – Renato Gama Sep 6 '14 at 16:17
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I think that your algorithm would consume lots of memory for huge numbers! But very nice anyways!! Good in the case that you want get the numbers progressively, like... streaming the numbers instead of having all of them at once! \$\endgroup\$ – Renato Gama Sep 5 '14 at 19:45
0
\$\begingroup\$

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.)

\$\endgroup\$

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.