Сообщение от
AI!
А ничего что я уже написал сей макрос?
Который генерирует число от 0 до n без повторений, где n произвольное, меньше 1024.
А называется макрос rnd1024.
Поясню, что я имею ввиду: по сути, задача "выборки n значений от 0 до n-1 без повторений" эквивалентна задаче "генерации случайной перестановки чисел от 0 до n-1" (по-английски это random shuffle)
1) Задача random shuffle обычно решается через массив: Тасование Фишера–Йетса
Если бы было можно просто "брать и генерировать очередное значение", то такой алгоритм наверняка бы упомянули в wikipedia. Но, нет, там про тасовку значений пишут, что всё-таки нужен массив, и при реализации Фишера–Йетса нужно быть внимательным, т.к. легко ошибиться и тасовка станет очень плохой.
Кстати, в OSCAT функция _ARRAY_SHUFFLE неправильная (там в 2 раза меньше перестановок чем надо, там плохой генератор и т.п.): https://github.com/simsum/oscat/blob...LE.EXP#L27-L34
Следующий момент -- для генерации перестановки большого количества элементов нужен ГСЧ очень высокого качества.
Например, из 1024 элементов есть 1024! перестановок. Для кодирования такого количества нужно log(1024!, 2) бит информации, т.е. примерно 8769 бит.
Это почти в 70 раз больше, чем внутреннее состояние xorshift128. Т.е. нужен либо ГСЧ с большим состоянием, либо нужно эффективно подмешивать энтропию "по ходу генерации". Да, тактование (выборка результата ГСЧ в случайный момент) является одним из таких действий, но тут большой вопрос сколько бит энтропии даёт подобное действо.
Получается, нужно крайне аккуратно следить за ГСЧ, иначе большая часть "возможных перестановок" вообще никогда не будет сгенерирована.
2) Есть ещё второй вариант -- pseudorandom permutation. Более известное как "симметричный шифр".
Например если есть алгоритм шифрования, шифрующий значения 0..63 с помощью ключа K, то "псевдослучайную перестановку" можно получить, если зашифровать значения 0, 1, 2 и т.п. последовательно. Т.е. Encrypt(0, K), Encrypt(1, K), и так далее. Разумеется, после каждого цикла нужно менять ключ шифрования и/или алгоритм шифрования.
Но тут 2 вопроса: во первых, ключ шифрования должен быть немалой длины (ну, чтобы хотя бы в теории закодировать все возможные n! перестановок), а во-вторых, на ум не приходят алгоритмы шифрования, у которых входной-выходной диапазон можно менять как параметр.
Ну, можно найти семейство алгоритмов, которые работают в числах 0...2n-1. В частности, 0..63, но если понадобится генератор "от 0 до 62 без повторений", то нужно будет ещё что-то придумывать.
Например, сработает такой алгоритм (но внутренний цикл while(nextValue>n) неудобно реализовывать на ОЛ):
Код:
int n=49; // хотим получить перестановки от 0 до n
int k=42; // ключ шифрования
for(int i=0; i < n; i++) {
int nextValue = Encrypt(i, k); // Считаем, что Encrypt выдаёт значения от 0 до 63
while(nextValue > n) { // Если оказалось 50..63, то значение не подходит -- шифруем его пока не попадёт в диапазон 0..49
nextValue = Enrcypt(nextValue, k); // да, повторно шифруем значение, если оно выходит за диапазон
}
System.out.println("next value = " + nextValue);
}
Для справки, ln(64!)/ln(2) == 296. Т.е. для описания всех возможных 64! перестановок нужно почти 300 бит энтропии.
3) Идея с "давайте просто запоминать выпавшие числа, и если выпадет повторно, то бросать кость заново" понятна, но в ОЛ это убого, и приходится идти на уступки вида "если значение уже было, то возьмём просто следующее свободное". Это самое "следующее свободное" нарушает "случайность" перестановки -- т.е. генератор генерирует biased (как оно по-русски? смещённые? неравномерно распределённые?) последовательности.
электронщик до мозга костей и не только