Is it possible to generate in pseudo-random ORDER all the numbers from 0 .. N, without repeating any number AND w/o keeping track of what numbers were already generated

F.e. the opposite, a non-random rule would be:

 - generate all ODD values
 - generate all EVEN values

does:

 np.random.choice(range(1000000),1000000,replace=False)

materialize the range ?

CodePudding user response：

Yes, it's possible.

You could create a custom LCG for your given N or the next power of two greater than your N, but the quality of the random numbers is quite bad.

A better method is to create a seeded hash function that is reversible for every power of two, and hash all numbers from 0 to next_pow_2(N), whiles rejecting numbers greater than N. This article explains it quite well: https://andrew-helmer.github.io/permute/

The above method works best if N isn't that small (N > 2^14 for the implementation in the linked article would be advisory), because creating good hash functions for a small input width is very hard.

Note that while these methods work, you should really consider just shuffling an array of numbers 0 to N, as that is usually faster than the above methods.

CodePudding user response：

Shuffle all the numbers in the range, then pick them off in the shuffled order.

More work, would be to develop a format preserving encryption that only produces numbers in the required range, and then encrypt the numbers 0, 1, 2, 3, ... Because encryption is a one-to-one mapping with a given key, different inputs are guaranteed to produce different outputs.

Whatever method you use you will only be able to output as many unique numbers as there are in the initial range, obviously. After that, the numbers will start to repeat.