Как использовать Mersenne Twister для генерации всех значений между двумя числами ровно один раз

Question

Я хотел бы использовать mt19937 для перебора массива и получения каждого значения от него ровно один раз, но в случайном порядке. По сути, есть ли способ использовать mt19937 для генерации всех чисел в определенном диапазоне ровно один раз (без просто игнорирования дубликатов, но при условии, что он не производит дубликатов вообще (ради эффективности))?

Я рассмотрел функцию тасования, однако это только те индексы, которые меня волнуют; значения внутри массива произвольны, но их соответствующий индекс важен. У меня есть матрица из 1, и мне нужно случайным образом выбрать индекс и превратить это значение 1 в 0. Но я не хочу выполнять этот расчет больше, чем это необходимо (ровно столько же элементов, сколько и в матрице).

Answer 1

Итак, вам нужно создать список значений, а затем перетасовать их.

Хотя есть функция перетасовки, алгоритм прост. Начните с индекса 0 и замените его случайным значением в диапазоне от 0 до N-1, затем перейдите к индексу 1 и поменяйте со случайным значением в диапазоне от 1 до N-1 и т. Д. Не переключайтесь на 0 до N-1, поскольку это не обеспечивает подлинно случайной перестановки.

Answer 2

Если предположить, что массив имеет размер N и вы не хотите, чтобы изменить его:

1. Сформировать второй массив, а также от размера N.
2. Смешайте второй массив, используя Fisher-Yates-Knuth shuffle.
3. Используйте элементы первого массива в порядке, указанном вторым массивом.

Фишер-Yates-Кнута перетасовать может быть реализован следующим образом:

//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] 

Вы также можете использовать std::shuffle:

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