Генератор псевдослучайных чисел без повторов: различия между версиями

Материал из sysadm
Перейти к навигации Перейти к поиску
Строка 15: Строка 15:
 
Наличие повторов в генераторе псевдослучайных чисел делит множество диапазона на несколько не пересекающихся колец, что не позволяет перебрать весь диапазон.
 
Наличие повторов в генераторе псевдослучайных чисел делит множество диапазона на несколько не пересекающихся колец, что не позволяет перебрать весь диапазон.
  
Есть подозрение, что данная формула генерирует одно кольцо полного перебора при любых P и q удовлетворяющих описанным выше условиям.
+
К сожалению, данная формула не является универсальной и порождает повторы при других P и m.
 +
Например P=1009, m=6 порождает несколько колец и не позволяет перебрать все числа в рамках одной последовательности.
 
</pre>
 
</pre>
  

Версия 00:56, 19 октября 2025

Ni+1 = Ni*q - [Ni*q/P]*P

квадратные скобки здесь обозначают выделение целой части
P - простое число, задающее границу диапазона
q = P - 3^m  (выбирается близкое к P/2)

При P=101, m=3, q=74, получаем псевдослучайную последовательность чисел в диапазоне 1-100 без повторов.
Данная формула использовалась в программе "Морской бой" для программируемого калькулятора MK-54, опубликовано в журнале "Техника молодежи" 1986 №10
Отсутствие повторов позволяло полностью перебрать все клетки поля 10x10 псевдослучайным образом.

В калькуляторе была встроенная функция генерации псевдослучайных чисел, но она не использовалась, потому что порождала повторы и не могла сформировать полный случайный перебор.
Повтор замыкает псевдослучайную последовательность в кольцо.
Наличие повторов в генераторе псевдослучайных чисел делит множество диапазона на несколько не пересекающихся колец, что не позволяет перебрать весь диапазон.

К сожалению, данная формула не является универсальной и порождает повторы при других P и m.
Например P=1009, m=6 порождает несколько колец и не позволяет перебрать все числа в рамках одной последовательности.

Пример кода на Python

def rand(N):
  return N*q-int(N*q/P)*P

P=101
m=3
q=P-3**m

R=rand(37)
print(R)
for i in range(100):
  R=rand(R)
  print(R)