How to select nth random integer from a range of integers without repetition or storage?-CodePudding

Let's say my system needs to provide a unique integer id regularly, between 1 and 1^20, from a function like --

function getNextRandomUniqueId(index:BigInt, min:BigInt, max:BigInt, seed:BigInt): BigInt { ? }

id = getNextRandomUniqueId(index=42, min=1, max=1^20, seed=0)

These ids need to be provided in random order as the index increases, not sequentially. Once an id has been provided, it cannot be provided again, as long as the index increases. My system cannot store a random list of all the numbers to be issued, or all the numbers issued, there's too many. I also don't want to rely on something like a random UUID, which is exceedingly unlikely to have a collision, but not guaranteed to.

How can this be done? To have a deterministic mathematical way to iterate randomly through a set of sequential integers without repetition and without storage?

CodePudding user response：

You cannot guarantee that your same id is not in another seed sequence.

Most languages use the time to generate the sequence when you are not providing a seed yourself. You have set your seed to zero so each time you restart your program, you will get your same ids. This is most likely not your intent :-)

But even when you would do this, the chance that you hit the same id is there. 1 in the 100,000,000,000,000,000,000.

The reason you can get the same id is because it is RANDOM

I would go with a GUID. 1 in the 340.280.000.000.000.000.000.000.000.000.000.000.000

CodePudding user response：

You can do it using the following formula:

x = (x   large_prime) % range

Since gcd(large_prime, range) = 1, in range steps x will visit every value in [0..range) exactly once.

The bigger the large_prime is compared to range, the less "predictable" is resulting sequence.

Note, this approach is not a "true" random, it is pseudo-random, as it follows a pattern. It's not possible to have true random approach with O(1) space limitation.

CodePudding user response：

This can be done, assuming you are allowed to store an encryption key and counter. Encryption is a one-to-one mapping so by encrypting all the numbers in a given range you will get back all those same numbers in a randomized order. Different keys will give a different order. Encrypt the numbers 0, 1, 2, 3, ... in order, using the key and keeping track of how far you have got.

Depending on the range of numbers, you may need to use some form of Format Preserving encryption to keep the outputs within the required range.