Генерация переставленного диапазона с помощью PRNG вместо перестановки
4 ответа
На основе ответ Jason , я сделал простую простую реализацию в C#. Найдите следующее самое большое питание двух больших, чем N. Это делает его тривиальным для генерации a и c, так как c должен быть относительно главным (значение, что это не может быть делимым 2, иначе нечетным), и (a-1) должно быть делимым 2, и (a-1) должно быть делимым 4. Статистически, должно потребоваться 1-2 соответствия для генерации следующего числа (так как 2 Н> = M> = N).
class Program
{
IEnumerable<int> GenerateSequence(int N)
{
Random r = new Random();
int M = NextLargestPowerOfTwo(N);
int c = r.Next(M / 2) * 2 + 1; // make c any odd number between 0 and M
int a = r.Next(M / 4) * 4 + 1; // M = 2^m, so make (a-1) divisible by all prime factors, and 4
int start = r.Next(M);
int x = start;
do
{
x = (a * x + c) % M;
if (x < N)
yield return x;
} while (x != start);
}
int NextLargestPowerOfTwo(int n)
{
n |= (n >> 1);
n |= (n >> 2);
n |= (n >> 4);
n |= (n >> 8);
n |= (n >> 16);
return (n + 1);
}
static void Main(string[] args)
{
Program p = new Program();
foreach (int n in p.GenerateSequence(1000))
{
Console.WriteLine(n);
}
Console.ReadKey();
}
}
Кажется, что Вы хотите алгоритм, который, как гарантируют, произведет цикл от 0 до n-1 без любых повторений. Существует почти наверняка целый набор их в зависимости от Ваших требований; теория групп была бы самым полезным ответвлением математики, если Вы хотите копаться в теории позади него.
, Если Вы хотите быстро и не заботитесь о шаблонах предсказуемости/безопасности/статистической, LCG является, вероятно, самым простым подходом. Страница Википедии, с которой Вы связались, содержит этот (довольно простой) набор требований:
период общего LCG в большей части m, и для некоторых вариантов намного меньше, чем это. LCG будет иметь целый период если и только если:
- c и m являются относительно главными,
- - 1 является делимым всеми простыми множителями m
- - 1, является кратным 4, если m является кратным 4
, С другой стороны, Вы могли бы выбрать период N> = n, где N является самым маленьким значением, которое имеет удобные числовые свойства, и просто отбросьте любые значения, произведенные между n и N-1. Например, самый низкий N = 2 <глоток> k - 1> = n позволил бы Вам использовать линейные сдвиговые регистры обратной связи (LFSR). Или найдите свой любимый криптографический алгоритм (RSA, AES, DES, безотносительно) и, учитывая конкретный ключ, выясните пространство N чисел, которые это переставляет, и для каждого шага применяют шифрование однажды.
, Если n является маленьким, но Вы хотите, чтобы безопасность была высока, это - вероятно, самый хитрый случай, поскольку любая последовательность S, вероятно, будет иметь период N намного выше, чем n, но также нетривиальна для получения не повторяющейся последовательности чисел с более коротким периодом, чем N. (например, если бы Вы могли бы взять вывод модификации S n и последовательности чисел неповторения гарантии, которая дала бы информацию о S, который взломщик мог бы использовать)
См. мою статью о безопасные перестановки с блочными шифрами для одного способа сделать это.
Изучите Линейные Сдвиговые регистры Обратной связи, они могут использоваться для точно этого. Короткий способ объяснить их состоит в том, что Вы запускаете с семени и затем выполняете итерации использования формулы
x = (x << 1) | f(x)
, куда f (x) может только возвратиться 0 или 1.
при выборе хорошей функции f x циклически повторится через все значения между 1 и 2^n-1 (где n является некоторым числом), хорошим, псевдослучайным способом. Функции в качестве примера могут быть найдены здесь , например, для 63 значений можно использовать
f(x) = ((x >> 6) & 1) ^ ((x >> 5) & 1)