An answer to this question on Stack Overflow.

Question

I would like to use mt19937 to loop over an array and grab each value from it exactly once, but in a random order. Essentially, is there a way to use mt19937 to generate all numbers within a particular range exactly once (without just ignoring duplicates, but ensuring that it does not produce duplicates altogether(for the sake of efficiency))?

I have considered a shuffle function, however it's only the indices I care about; the values within the array are arbitrary, but their corresponding index is important. I have a matrix of 1's and I need to randomly select an index and turn that 1 to a 0. But I don't want to perform this calculation more than is necessary (exactly as many elements as are in the matrix).

Answer

Assuming your array is of size N and you don't want to rearrange it:

1. Generate a second array, also of size N.
2. Shuffle the second array using the Fisher-Yates-Knuth shuffle.
3. Utilize the elements of the first array in the order specified by the second array.

The Fisher-Yates-Knuth shuffle can be implemented as follows:

//To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
  j ← random integer such that i ≤ j < n
  swap a[i] and a[j]

You could also use std::shuffle:

std::shuffle(a.begin(), a.end(), std::default_random_engine(seed));