Pseudo random permutation of a very large number of elements

Question

Consider a file $\textbf{F}$ containing $n$ distinct elements, located on a hard drive. Given the large size of $n$, it's not feasible to load the entire file $\textbf{F}$ into main memory. Assuming we have access to a pseudo-random generator capable of producing a (pseudo) random sequence of $m$ elements, the question arises: How can we generate a pseudo-random permutation of the elements in $\textbf{F}$, with the result stored on a hard drive?

---

$\textbf{Edit:}$
As an example, the practical case I wanted to address is as follows:
The file $\textbf{F}$ comprises $n=1.5 \times 10^9$ strings, each consisting of $80$ characters.
I would like to have the first $p=100 \times 10^6$ elements of a random permutation of file $\textbf{F}$.
I don't know the exact value of $m$, but given my memory capacity, I believe $m=5 \times 10^6$.

Answer 1

Assuming you want the entire permutation, or a significant portion of it, the following algorithm which I call RadixShuffle is an efficient and simple way to shuffle larger-than-memory (or even larger-than-cache) data:

1. Choose a radix $r$ (recommended values are powers of two, $r = 2$, $r = 4$, $r = 16$, $r = 256$ can all be good choices depending on the circumstances, this makes random number generation efficient).

2. Initialize buckets $b_1, \dots, b_r$. Loop over your data and assign each element to a random bucket.

3. For each $i$ shuffle the elements within each bucket $b_i$.

4. Output the concatenated buckets $b_1, \dots, b_r$.

Step 2 can be done for arbitrarily large data that doesn't fit in memory by flushing buckets to disk when they cross a certain size.

Step 3 can be done recursively with RadixShuffle, or you can switch to a different algorithm once the data does fit in memory.

After computing the buckets you only need to recurse on those buckets you are interested in in Step 3. For example, if you only need the first $k$ elements from the permutation you can discard every bucket $b_j$ as long as $\sum_{i=1}^{j-1} |b_i| \geq k$.

If you have a seedable RNG it may be more efficient to first compute the bucket sizes before performing the algorithm. If you do this you can even perform the entire algorithm in-place (another way to do it in-place is by using $r = 2$, see Hoare's partitioning method (you can even do it in-place for arbitrary $r$ without pre-computation, but it gets complicated, see the IPS4o sorting algorithm for how that works)). You can then also (if you are interested in subsets of the shuffled data) avoid having to write and/or flush buckets to disk that you will never read again.

---

You can prove this is a correct unbiased shuffle algorithm by interpreting the sequence of bucket indices assigned to element a particular element as a base-$r$ fractional number $0.abcd\dots$, which is the prefix of a real random number between $[0, 1)$. Then RadixShuffle is a sorting algorithm using this real random number as the key, which is a uniform unbiased shuffle.