Генерация случайных чисел от 1 до n без дублирования в пространстве O (1)

Question

Один из способов - использовать массив размером n, такой, что a[i]=i.

Теперь перемешайте его.

Затем используйте цикл для печати чисел.Но можно ли это сделать без использования массива?

Ps: Пожалуйста, не используйте встроенную функцию генератора случайных чисел.Я пытаюсь получить логический ответ и написать эту случайную функцию самостоятельно.

Answer 1

Я бы сказал, что это зависит от качества случайных чисел, которые вы хотите получить.

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

Несколько более правдоподобное решение - взять некоторое простое число p > n и некоторое целое число a > 1, которое является примитивным корнем по модулю p, а затем посмотретьв a mod p, a^2 mod p, a^3 mod p, ..., a^{p-2} mod p.Это будет перестановка чисел 2, 3, ..., p - 1.Откажитесь от всего, что больше n, и выведите остальное.(И вставьте отсутствующий 1 в случайную позицию.) Все это можно сделать в O (1) дополнительной памяти, многократно делая x -> (x*a) mod p и отбрасывая элементы > n на лету.И результат может быть достаточно случайным для некоторых приложений: при правильном выборе a он, по крайней мере, будет выглядеть довольно случайным для неподготовленного человеческого глаза.Тем не менее, не намного больше.

Для получения качественных случайных чисел, я сомневаюсь, что есть общее решение, которое использует O (1) дополнительную память.Но не верьте мне на слово.Давайте посмотрим, что могут дать другие ответы.

Answer 2

Этот ответ основан на python, но вы можете общаться с любым другим языком программирования, который вам нравится.

import random # using random class
some_num = _ # any number
sample_num = _ # this should be less than or equal some_num
for num in random.sample(range(some_num), sample_num):
    print(num)

Это генерирует случайные числа и печатает их, используя цикл.