Генерация беспристрастного случайного списка

Question

Постановка задачи

Мне нужно смоделировать процесс 100 Проблема узника , в котором каждый ящик шкафа размером 100 содержит уникальное число от 0 до 99. Я инициализирую количество ящиков следующим образом:

def arrange_event(n_prisoners=100):
    if (n_prisoners % 2) != 0 or n_prisoners <=0:
        raise ValueError("Number of prisoners must be a postive and even number.")
    drawer = list(range(n_prisoners))
    random.shuffle(drawer)
    return drawer

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

Примечание

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

Вот что я нашел в официальном документе , который предполагает, что распределение вероятностей по перестановкам в моей реализации смещено с использованием random.shuffle().

random.shuffle (x [, random])

Перемешайте последовательность x на месте. Необязательный аргумент random - это функция с 0 аргументами, возвращающая случайное число с плавающей точкой в ​​[0.0, 1.0); по умолчанию это функция random ().

Обратите внимание, что даже для довольно небольших len (x) общее число перестановок x больше, чем период большинства генераторов случайных чисел; это подразумевает, что большинство перестановок длинной последовательности никогда не может быть сгенерировано.

Answer 1

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

def arrange_event(n_prisoners=100):
    if (n_prisoners % 2) != 0 or n_prisoners <=0:
        raise ValueError("Number of prisoners must be a postive and even number.")
    drawer = list(range(n_prisoners))
    for i in range(n_prisoners, 1, -1):
        random_index = random.choice(range(i))
        swap_a, swap_b = drawer[random_index], drawer[i-1]
        drawer[random_index], drawer[i-1] = swap_b, swap_a
    return drawer