Say you want to iterate over a sequence [0 to n] in a random order, visiting every element exactly once. Is there any way to do this in O(1) memory, i.e. without creating an [1..n] sequence with std::iota and running it through std::random_shuffle?
Some kind of iterator spitting out the sequence in a random order would be optimal.
A requirement is that it should be possible to get another random order by picking another seed.
In theory, if you built a random number generator whose period was exactly n, and covered all values in 0..n, then running through this once would give you what you like.
Of course, this may not be a general solution, at least if you are looking for something dynamic, since you would have to pre-create the PRNG and how you do this depends on n.