Is it possible to iterate over an array in random order?

Question

So, suppose I have an array:

int arr[5];

Instead of iterating through the array from 0 to 4, is it possible to do that in random order, and in a way that the iterator wouldn't go through the same position twice?

Sure, you just have to implement a custom iterator that does that. C++ can do anything. Did you try implementing your own custom iterator that does this? — Sam Varshavchik, Jan 04 '21 at 00:03
Depending on the size of the array, you might be better of just using [`suffle`](https://en.cppreference.com/w/cpp/algorithm/random_shuffle) on it and then iterate like normal — NathanOliver, Jan 04 '21 at 00:05
Or generate a second array of integers, containing the values `0` to `4`. Shuffle that second array, and use its elements as indices for the first. — Peter, Jan 04 '21 at 00:11
@SamVarshavchik not really, I didn't know that was a thing. I'll look it up — wintersun, Jan 04 '21 at 00:12
@wintersun How random does it have to be, for example do you need to guarantee that all possible permutations occur? If not, one cheap way to do it could be to choose a random start index `n` between 0 and 4, and a random step `k` between 1 and 4, then iterate over indexes `n = (n + k) % 5`. That will give you 20 different permutations while requiring no additional space and negligible extra time compared to the plain index increment. — dxiv, Jan 04 '21 at 00:31
Nearly a duplicate of a much older question: https://stackoverflow.com/q/10054732/179910, but that's more specific about the mechanism, and eliminates the possibility of shuffling an auxiliary array of indices. — Jerry Coffin, Jan 04 '21 at 01:15

score 3 · Answer 1 · answered Jan 04 '21 at 00:18

All the below assumes you want to implement your iteration in O(1) space - not using e.g. an auxiliary array of indices, which you could shuffle. If you can afford O(n) space, the solution is relatively easy, so I assume you can only afford O(1).

To iterate over an array in a random manner, you can make a random number generator, and use its output as an index into the array. You cannot use the standard RNGs this way because they can output the same index twice too soon. However, the theory of RNGs is pretty extensive, and you have at least two types of RNG which have guarantees on their period.

To use these theoretical ideas:

Choose a number N ≤ n (where n is the size of your array), but not much greater than n, such that it's possible to construct a RNG with period N
Call your RNG N times, so it generates a permutation of numbers from 0 to N-1
For each number, if it's smaller than the size of your array, output the element of your array with that index

The techniques for making a RNG with a given period may be too annoying to implement in code. So, if you know the size of your array in advance, you can choose N = n, and create your RNG manually (factoring n or n+1 will be the first step). If you don't know the size of your array, choose some easy-to-use number for N, like some suitable power of 2.

score 1 · Answer 2 · answered Jan 04 '21 at 00:21

As mentioned in the comments, there are several ways you can do this. The most obvious way would be to just shuffle the range and then iterate over it:

std::shuffle(arr, arr + 5);

for (int a : arr) 
  // a is a new random element from arr in each iteration

This will modify the range of course, which may not be what you want.

For an option that doesn't modify the range: you can generate a range of indices, shuffle those indices and use those indices to index into the range:

int ind[5];
std::iota(ind, ind + 5, 0);
std::shuffle(ind, ind + 5);

for (int i : ind)
  // arr[i] is a new random element from arr in each iteration

You could also implement a custom iterator that iterates over a range in random order without repeats, though this might be overkill for the functionality you're trying to achieve. It's still a good thing to try out, to learn how that works.

Is it possible to iterate over an array in random order?

2 Answers2