language agnostic - Iterator to produce unique random order?

Question

The problem is stated as follows, we have a very large number of items which are traversed through an iterator pattern (which dynamicaly constructs or fetches) the requested item.

Due to the number of items being large and thus cannot be kept in memory (as a list for example).

What is a procedure for the iterator to follow in order to produce a random order of the items each time the iterator is called. A unique random order means that eventually all items are traversed only once but returned in a random order.

if the number of items is relatively small, one can solve this problem as follows:

1. Store the items in a list in memory (or secondary memory)
2. Shuffle the list
3. Traverse the shuffled list.

For this question one can assume that the iterator can index the items (or rank/unrank them). So the iterator can fetch the ith item for all indices i in the range of items.

Note the random order should be uniformly distributed in the set of all orderings of the items or in other words be unbiased. This condition leaves out solutions which randomise the list of items in a block-by-block scheme (in order to have some of the items in memory for example and randomise only them, then the next block of items and so on)

Answer 1

Encryption is reversible, hence an encryption is a one-to-one mapping from a set onto itself.

Pick a block cypher with a large enough block size to cover the number of items you have.

Encrypt the numbers 0, 1, 2, 3, 4, ... This will give you a non-repeating ordered list of numbers up to 2^(block size).

If the encrypted number is too large, ignore it. If the encrypted number is within the size of your item list, then pick that item. Repeat for however many items you need.

A cypher with variable block-size (like the Hasty Pudding cypher) will reduce the number of misses.