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

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

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


c++ random algorithm mersenne-twister
person DrakeMurdoch    schedule 09.01.2017    source источник
comment
Посмотрите на shuffle.   -  person Jarod42    schedule 09.01.2017
comment
Вы сами пробовали решить эту проблему? Кроме того, эта проблема не связана с конкретным механизмом случайных чисел, который вы используете (mt19937).   -  person Xirema    schedule 09.01.2017
comment
Случайные числа генерируют дубликаты, иначе они не были бы случайными. Второе предложение @Jarod42 изучить std::shuffle.   -  person Mark Ransom    schedule 09.01.2017
comment
Из того, что я читал, Mersenne Twister ограничен диапазонами, основанными на 2 ^ n - 1. В зависимости от диапазона может быть LCG множитель, значение приращения и модуль, которые будут работать.   -  person rcgldr    schedule 10.01.2017

Ответы (2)


arrow_upward
1
arrow_downward

Предполагая, что ваш массив имеет размер N, и вы не хотите его переупорядочивать:

  1. Создайте второй массив, также размером N.
  2. Перетасуйте второй массив, используя перетасовку Фишера-Йейтса-Кнута.
  3. Используйте элементы первого массива в порядке, указанном вторым массивом.

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

//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));
person Richard    schedule 10.01.2017

arrow_upward
0
arrow_downward

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

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

person Malcolm McLean    schedule 10.01.2017
comment
Я рассматривал функцию перемешивания, но на самом деле меня интересуют только индексы; значения в массиве произвольны, но важен их соответствующий индекс. По сути, у меня есть матрица из 1, и мне нужно случайным образом выбрать индекс и превратить эту 1 в 0. Но я не хочу выполнять этот расчет больше, чем необходимо (ровно столько элементов, сколько есть в матрице). Теперь я понимаю, что мой первоначальный вопрос был довольно плохо сформулирован, извините. - person DrakeMurdoch; 10.01.2017