Simulate random iteration of array

Question

I have an array of given size. I want to traverse it in pseudorandom order, keeping array intact and visiting each element once. It will be best if current state can be stored in a few integers.

I know you can't have full randomness without storing full array, but I don't need the order to be really random. I need it to be perceived as random by user. The solution should use sub-linear space.

One possible suggestion - using large prime number - is given here. The problem with this solution is that there is an obvious fixed step (taken module array size). I would prefer a solution which is not so obviously non-random. Is there a better solution?

Answer 1

How about this algorithm?

To pseudo-pseudo randomly traverse an array of size n.

1. Create a small array of size k
2. Use the large prime number method to fill the small array, i = 0
3. Randomly remove a position using a RNG from the small array, i += 1
4. if i < n - k then add a new position using the large prime number method
5. if i < n goto 3.

the higher k is the more randomness you get. This approach will allow you to delay generating numbers from the prime number method.

A similar approach can be done to generate a number earlier than expected in the sequence by creating another array, "skip-list". Randomly pick items later in the sequence, use them to traverse the next position, and then add them to the skip-list. When they naturally arrive they are searched for in the skip-list and suppressed and then removed from the skip-list at which point you can randomly add another item to the skip-list.