How can I create a random number generator that can not generate the last value it generated?

Question

I want to create a random number generator that can not return the last value it generated. So far I have created a simple generator using Random.Range(0, 4), however this could return a value two times in a row, which is unwanted for my project. How can I improve on this code?

Answer 1

What you should do is create an integer representing the last random number returned by the number generator. Then you can run the generator in a while loop such that it never returns the same number it returned in the previous run.

int lastRandomNumber = -1;
int GiveRandomNumber()
{
  int randomNumber = lastRandomNumber;
  while(randomNumber==lastRandomNumber)
    randomNumber = Random.Range(0, 4);
  lastRandomNumber = randomNumber;
  return randomNumber;
}

Answer 2

There are several methods which can generate uniformly distributed values without repeating two values in a row. Disclaimer: I’m using pseudo-code below because don’t program C# — I’m interested in this question based on my 40+ year career using random numbers in the context of computer simulation modeling.

The first one is to use acceptance/rejection techniques, as described by obieFM. The following assumes that previousValue is accessible in the function and that the range arguments are [inclusive, exclusive). To generate from a set containing k distinct values:

previousValue = Random.Range(0, k)

function nonRepeatedRandom {
    newValue = Random.Range(0, k)
    while newValue == previousValue {
        newValue = Random.Range(0, k)
    }
    previousValue = newValue
    return newValue
}
    

The probability of terminating the loop on any given iteration is (k-1)/k. If the calls to Random.Range() produce independent values then the number of iterations has a Geometric distribution, and the average number of iterations is k/(k-1). The worst-case average is when k is 2, and will take an average of 2 iterations to generate each value. As k increases, the average number of iterations quickly converges towards 1. While there is no theoretical upper bound for the number of iterations, the probability of requiring more than n iterations is (1/k)ⁿ — you have to have duplicated the previousValue, with probability 1/k each time, n times in a row. For example, if k is 4 then the probability of needing more than 50 iterations to generate a value is 2^-100, a ridiculously small number — your odds of getting hit by lightning and then later killed by a meteor are about 18 orders of magnitude higher than this.

But fear not, my friends, if you have a morbid fear of probabilistic algorithms there’s a simple deterministic alternative available:

previousValue = Random.Range(0, k)

function nonRepeatedRandom {
    newValue = Random.Range(0, k-1)
    if newValue >= previousValue {
        newValue = newValue + 1
    }
    previousValue = newValue
    return newValue
}

For each value after the first one, you want to generate from a set of k-1 eligible values. We accept values below previousValue as-is, and promote values in the range [previousValue, k-2] by 1. The result spans the range [0, k-1], inclusive, excluding previousValue. It's trivial to extend this to work for non-zero lower bounds on the range.

If the values to be generated without sequential duplicates are non-contiguous numeric values or categorical values, enumerate them in an array and use the deterministic algorithm given above to generate the index of the next value to be returned.

You could also use shuffling of array elements or swapping the most recent value to the end of the array, but I think the mechanisms already provided are more efficient and effective for sequential numerical ranges so I won't go into further detail on these alternatives.

Answer 3

To code something more elegant and avoid an unwanted loop, you'll need to make an array where you'll remove the last number. If you want to simply remove one number which is the last random one, you can either reset (if the list is small enough like 0-4) or re-add the number in your list if it's very big.

In other words, if you want to re-create a list each time, it should look something like this:

var rand = new Random();

int[] randoms = new int[5];
int lastRandom = 2; // For exemple/start
int iter = 0;
for (int i = 0; i < randoms.Length; i++)
{
if (iter == lastRandom) iter++;
randoms[i] = iter++;
}
int newRandom = randoms[rand.Next(randoms.Length)];
Console.WriteLine(newRandom);

It may look overkill, but it's the most flexible and best way to do it. As like you said, if we simply re-roll the random, it can roll on it over and over which can make some lag (on large scale).