Returning random integer from interval based on last result and a seed

Question

Suppose we have an interval of integers [a, b]. I would like to have a function that returns random members from within the interval, without repetitions. Once that all members within the interval are explored, the function would start to return the same first random sequence again, in the same order.

Example: a=1, b=5

3, 1, 4, 5, 2, 3, 1, 4, 5, 2, 3, 1, 4, 5, 2, ...

This would be easy to achieve by shuffling an array of all elements between a and b, and repeating it once the array is finished. However, this would take too much memory space, and this is not suitable for my case (I might have millions of elements).

Instead, the function I'd like to have would be more or less like this:

f(a, b, n, seed) -> n+1

Where:

a - start of interval
b - end of interval
n - last element returned from list
seed - self-explanatory
n+1 - next random element from list, calculated by using the seed and the last element returned (n)

The trick is knowing some way to get a non-repeated number from the interval based only on the element returned before and the seed. In the end, it would behave like a circular list randomized at its initialization, but without using memory space.

Answer 1

I suggest you pick a random permutation on the range $[a,b]$, i.e., a bijective function $\pi:[a,b]\to [a,b]$. Then, maintain a counter $i$ that starts at $i=a$; at each step, output $\pi(i)$ and then increment $i$ (wrapping around so that $b+1$ becomes $a$).

There are standard methods for generating such a random permutation in the cryptography literature: look up format-preserving encryption. The seed is the cryptographic key. You will be able to compute $\pi(i)$ in $O(1)$ time and $O(1)$ space, so this should be very efficient and avoid the need for a lot of storage.

If you insist that the next output should be a function of the previous output, you can let $g(i)=i+1$ (except that $g(b)=a$), then let $f(i)=\pi^{-1}(g(\pi(i))$, where $\pi$ is a random permutation chosen as above. This will then give you a random cycle that iterates through the elements of $[a,b]$ in a random order. The outputs are the sequence $f(a),f(f(a)),f(f(f(a))),\dots$.