Идея случайного генератора, который имитирует перетасовку, хороша, если вы можете получить тот, чей максимальный период вы можете контролировать.
Linear Congruential Generator вычисляет случайное число с формулой:
x[i + 1] = (a * x[i] + c) % m;
Максимальный период м и это достигается тогда, когда выполнены следующие свойства:
- Параметры с и m относительно простые.
- Для каждого простого числа г разделяющей м, - 1 кратно г.
- Если м кратно 4, то также - 1 кратно 4.
Мой первый darft Приглашена делает м следующий кратное 4 после длины массива, а затем найти подходит a и c значения. Это была (а) большая работа и (б) давала очень очевидные результаты.
Я переосмыслил этот подход. Мы можем сделать м наименьшей мощностью двух, в которой будет располагаться длина массива. Единственный простой коэффициент m - это 2, что сделает каждое нечетное число относительно простым. За исключением 1 и 2, м будет делится на 4, что означает, что мы должны сделать - 1 кратно 4.
, имеющей большую м, чем длина массива означает, что мы должен отбросить все значения, которые являются незаконными индексами массива. Это произойдет не более, чем в любой другой момент и должно быть незначительным.
В следующем коде приведены псевдослучайные числа с периодом превышения m. Я избегал тривиальных значений для a и c и на моих (не слишком многочисленных) пятнах, результаты выглядели хорошо. По крайней мере, не было очевидного велосипедного рисунка.
Итак:
class RandomIndexer
{
public:
RandomIndexer(size_t length) : len(length)
{
m = 8;
while (m < length) m <<= 1;
c = m/6 + uniform(5 * m/6);
c |= 1;
a = m/12 * uniform(m/6);
a = 4*a + 1;
x = uniform(m);
}
size_t next()
{
do { x = (a*x + c) % m; } while (x >= len);
return x;
}
private:
static size_t uniform(size_t m)
{
double p = std::rand()/(1.0 + RAND_MAX);
return static_cast<int>(m * p);
}
size_t len;
size_t x;
size_t a;
size_t c;
size_t m;
};
Вы можете использовать генератор, как это:
std::vector<int> list;
for (size_t i = 0; i < 3; i++) list.push_back(i);
RandomIndexer ix(list.size());
for (size_t i = 0; i < list.size(); i++) {
std::cout << list[ix.next()]<< std::endl;
}
Я знаю, что это до сих пор не является большим генератором случайных чисел, но это достаточно быстро, не требует копии массива и, похоже, работает нормально.
Если подход к собиранию и гр случайным образом дает плохие результаты, это может быть хорошей идеей, чтобы ограничить генератор к некоторым степеням двойки и ценностям литературы трудно кода, которые оказались хорошо.
Вы довольны посещением данного элемента более одного раза или нет? т. е. вы ищете случайную перестановку элементов или для случайной последовательности элементов? Вопрос, который вы цитируете, касается первой из этих проблем (также называемой перетасовкой). – Walter
Множество (большинство?) Генераторов псевдослучайных чисел могут быть определены алгоритмом и целым числом или двумя, чтобы описать их текущее состояние. Учитывая эти факторы, их будущее поведение полностью детерминировано, хотя, по-видимому, случайное - вот что означает * псевдо *. Что вы ищете, это не PRNG? –
Очевидно, мне нужно избегать повторений (в противном случае я могу просто перейти к случайному элементу). Я редактировал вопрос, добавляя эту информацию. Фактически, желаемое решение должно сохранять текущее состояние таким образом, чтобы можно было перемещать N элементов из N шагов из любого состояния. – Michal