Random sequence iteration in O(1) memory?

Question

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.

Answer 1

If you could mutate the sequence in-place, you could simply repeatedly draw a random number from 0-N, and then erase the element you visited, or swap it to the end, or such schemes.