Just a quick note on a cryptography trick I learned many years ago, with thanks to #crypto on IRC.
If you wish to iterate a sequence of length in a random order you can use an ordinary index in the range , but use format-preserving encryption to transform it to another index. Since encryption is reversible with the key, and the output is the same size as the input, each index will appear exactly once in the output. Mathematicians and I would say format-preserving encryption is a pseudorandom permutation: it appears random, and it reorders a sequence without losing or duplicating any entries. So the output is a reordered sequence that we don’t need to store:
It gets neater. Note that we don’t even need to keep the original, in-order index anywhere; we can just decrypt the index of the current element, add or subtract something to move in either direction, and encrypt again.1 This also means we could jump to any point in the shuffled sequence and still easily know what's next. For the permutation above, the “next” function is:
You could therefore use a format-preserving encryption primitive to implement a perfect playlist shuffle that is entirely stateless.2 Given the complexity of some media players I’ve seen, I wonder if this might be a simplification.