Случайный выбор

Question

Учитывая два целых числа N и n (N> = n> 0), как мне генерировать случайный выбор (без повторений!) Из [0, N) с длиной = n? Например. При N = 5, n = 3 возможных решений: (3,0,2) или (2,4,1) и т. Д.

Существует ограничение, препятствующее использованию наивного подхода: использование памяти должно быть O (n), а не O (N).

/ * Под наивным подходом я подразумеваю использование временного массива размера = N, который изначально заполняется номерами 0..N-1 по порядку. Требуемые n элементов выбираются случайным образом из этого массива. * /

Answer 1

Пройдите все числа m от 0 до N, решая, включать ли m в набор при обнаружении.Вам необходимо обновить вероятность включения следующего числа на основе уже обработанных номеров.

Давайте применим эту идею к приведенному примеру с n = 3 и N = 5.Сначала рассмотрим m = 0.Осталось 3 числа и 5 вариантов, поэтому 0 находится в наборе с вероятностью 3/5.Используйте генератор случайных чисел, чтобы решить, включать число или нет.Теперь рассмотрим m = 1.Если вы включили 0 в набор, то у вас осталось 2 числа и 4 возможности, поэтому его следует включить с вероятностью 2/4, но если 0 не включено, у вас осталось 3 числа и 4 возможности и, следовательно, 1 должна быть включенас вероятностью 3/4.Это продолжается до тех пор, пока необходимые 3 числа не будут включены в набор.

Вот реализация на Python:

from __future__ import division
import random

def rand_set(n, N):
    nums_included=set()
    for m in range(N):
        prob = (n-len(nums_included)) / (N-m)
        if random.random() < prob:
            nums_included.add(m)
    return nums_included

Вы можете (и, вероятно, должны) добавить в тест, чтобы увидеть, когда вы 'В вашем наборе достаточно номеров и вырваться из цикла рано.

Числа хранятся в наборе, размер которого варьируется от 0 до n, поэтому используется хранилище O(n).Все остальное использует постоянное пространство, поэтому оно в целом O(n).

EDIT На самом деле, вы можете пойти немного дальше с этим подходом, чтобы он занимал постоянное пространство.В Python просто создайте генератор на основе вышеизложенного:

def rand_set_iter(n, N):
    num_remaining = n
    m = 0
    while num_remaining > 0:
        prob = num_remaining / (N-m)
        if random.random() < prob:
            num_remaining -= 1
            yield m
        m += 1

Здесь я пошел дальше и использовал цикл while вместо цикла for.Чтобы сохранить результаты, вам, конечно, нужно использовать O(n) пробел.Но если все, что вам нужно сделать, это перебрать числа, версия генератора сделает это в O(1).

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

Answer 2

Простое (но потенциально очень неэффективное) решение *1001* состоит в том, чтобы просто создать список, многократно выбирая значение в желаемом диапазоне и проверяя, выбрали ли вы его уже или нет.Это имеет неограниченное максимальное время, потому что вы могли бы всегда заканчивать тем, что случайно выбрали что-то, что вы уже выбрали.

Я имею смутное подозрение O (n ² ) решение, которое на каждой итерации выбирает значение в диапазоне [0, N - i), где i - это количество элементов, которое вы уже получили ... и затем отображает это новое значение в диапазоне [0, N), просматривая существующеевыбранные элементы и добавление 1, если вы обнаружите, что вы уже получили значение, меньшее или равное выбранному вами значению.Тебе нужно тщательно обдумать это, но это эффективный подход, который я рассмотрю.

Answer 3

В python это было бы действительно просто:

selection = random.shuffle(range(N))[:n]

Это O (N) в памяти, так как список допустимых значений сначала генерируется, а затем перетасовывается на месте, поэтому он не работает на вашем компьютере.требование: (

Вы можете попробовать что-то вроде этого:

N = 5
n = 3
selection = set()
while len(selection) < n:
    selection += pick_random_int(0, N)

По сути, это то, что предложил Джон Скит. Это будет хорошо работать при n << N, но начать ужасно проваливаться с nблизко к N. в этом случае, хотя, О (п) и O (N) памяти решения будут сходиться в любом случае и ваше требование является спорным;) </p>

Answer 4

Разделите интервал [0, N] на n интервалов. Из каждого интервала выберите случайное число, а затем рандомизируйте результат. Проблема в том, что в этой ситуации распределение не является унифицированным.