Все числа в данном диапазоне, но в случайном порядке

Question

Допустим, я хочу сгенерировать все целые числа от 1 до 1000 в случайном порядке. Но...

• Числа не генерируются более одного раза
• Без хранения массива, списка... всех возможных чисел
• Без сохранения уже сгенерированных номеров.
• Не пропуская ни одного номера в конце.

Я думаю, что это должно быть невозможно, но, возможно, я просто не думаю о правильном решении.

Я хотел бы использовать его в C#, но меня больше интересует подход, чем фактическая реализация.

Answer 1

Шифрование. Шифрование - это взаимно-однозначное сопоставление двух наборов. Если два набора одинаковы, то это перестановка, указанная ключом шифрования. Напишите / найдите шифрование, которое отображает {0, 1000} на себя. Читайте о форматном сохранении шифрования (FPE), чтобы помочь вам здесь.

Для генерации случайного порядка просто зашифруйте числа по порядку 0, 1, 2, .... Вам не нужно хранить их, просто следите за тем, как далеко вы прошли через список.

С практической точки зрения, с числами в {0, 1023} было бы легче иметь дело, поскольку это был бы блочный шифр с размером блока 10 битов, и вы могли бы написать простой шифр Фейстеля для генерации ваших чисел. В любом случае вы можете захотеть сделать это и просто зашифровать числа выше 1000 - метод обхода цикла FPE.

Answer 2

Если случайность не является основной проблемой, вы можете использовать линейный конгруэнтный генератор. Поскольку LCG не будет генерировать последовательности максимальной длины, когда модуль представляет собой простое число, вам нужно будет выбрать больший модуль (следующая наибольшая степень 2 будет очевидным выбором) и пропустить любые значения за пределами требуемого диапазона.

Боюсь, C# на самом деле не моя вещь, но, надеюсь, следующий Python говорит само за себя. Это потребует небольшой доработки, если вы хотите создавать последовательности в очень небольших диапазонах:

# randint(a, b) returns a random integer in the range (a..b) (inclusive)
from random import randint

def lcg_params(u, v):
    # Generate parameters for an LCG that produces a maximal length sequence
    # of numbers in the range (u..v)
    diff = v - u
    if diff < 4:
         raise ValueError("Sorry, range must be at least 4.")
    m = 2 ** diff.bit_length()              # Modulus
    a = (randint(1, (m >> 2) - 1) * 4) + 1  # Random odd integer, (a-1) divisible by 4
    c = randint(3, m) | 1                   # Any odd integer will do
    return (m, a, c, u, diff + 1)

def generate_pseudorandom_sequence(rmin, rmax):
    (m, a, c, offset, seqlength) = lcg_params(rmin, rmax)
    x = 1         # Start with a seed value of 1
    result = []   # Create empty list for output values
    for i in range(seqlength):
        # To generate numbers on the fly without storing them in an array,
        # just run the following while loop to fetch a new number
        while True:
            x = (x * a + c) % m             # Iterate LCG until we get a value in the
            if x < seqlength: break         # required range
        result.append(x + offset)           # Add this value to the list
    return result

Пример:

>>> generate_pseudorandom_sequence(1, 20)
[4, 6, 8, 1, 10, 3, 12, 5, 14, 7, 16, 9, 18, 11, 20, 13, 15, 17, 19, 2]