Shuffling a collection too large for memory

Question

I have a set that is too large to hold in memory but I have a function that I can use to compute a value within the set given an index. I'm curious if there's a standard way to shuffle this set, a pseudo-shuffle is acceptable and expected.

I imagine a function that is initialized with some parameters, including the size of the set to be shuffled, and that I can call repeatedly, getting unique and pseudo-random indexes each time that I can use to generate the corresponding value in my set. I also imagine that this function is periodic and repeats after I've gone through all values once (so there's some mod relation).

This function need not be cryptographically secure but rather be easy to construct and hold in memory so that the next "random" value of the set may be generated.

---

Here's a concrete formulation of the problem. I want to iteratively generate "random" colors in the RGB spectrum without repeats. I don't want to create an array of 256^3 elements and shuffle them. I want a function that on each call provides an index in the range that I have not yet received, until I've exhausted the range.

How might you construct a function that satisfies the above?

Answer 1

Let $n$ denote the number of items in the set, and $f(i)$ denote the $i$th value. Use format-preserving encryption to construct a random permutation $\sigma:\{1,\dots,n\} \to \{1,\dots,n\}$. Define $g(i) = f(\sigma(i))$. Then $g$ is a representation of a randomly shuffled version of your set, and specific items can be accessed very efficiently.

---

To address your concrete problem, you'd pick a random permutation on $\{0,1\}^{24}$, i.e., $\sigma : \{0,1\}^{24} \to \{0,1\}^{24}$. This can be done using format-preserving encryption: format-preserving encryption will give you a block cipher $E:K \times \{0,1\}^{24} \to \{0,1\}^{24}$ such that if you pick a key $k \in K$ random, $E_k$ will be (indistinguishable from) a random permutation on $\{0,1\}^{24}$. Moreover, $E_k$ can be efficiently evaluated. Then, if you want $m$ random RGB colors, you'd pick a random key $k$ and output the $m$ colors $E_k(0), E_k(1), \dots, E_k(m-1)$.

A reasonable way to build a 24-bit block cipher is to use a Feistel cipher on 24 bits: say, 4 rounds, where in the $i$th round you map the input $L||R$ to the output $R||(L \oplus f_k(R,i))$, where $L,R$ are each 12 bits long and $f_k$ is a PRF, say $f_k = AES_k(R||i)$, and $||$ denotes concatenation of bits. You can adjust the number of rounds (fewer rounds is faster; more rounds gives higher amount of pseudorandomness; you probably want at least 3 rounds), and you can adjust the choice of $f$ (for instance, instead of a cryptographic-based construction, you could use any fast, non-cryptographic hash function). This is the construction proposed in https://en.wikipedia.org/wiki/Format-preserving_encryption#FPE_from_a_Feistel_network. I suggest referring to the Wikipedia link I shared above for an overview of standard constructions for format-preserving encryption.