Выберите N предметов в случайном порядке из последовательности неизвестной длины

Я пытаюсь написать алгоритм, который бы выбирал N отдельных элементов из последовательности в произвольном порядке, не зная заранее размера последовательности, и где было бы дорого повторять последовательность более одного раза. Например, элементы последовательности могут быть строками огромного файла.

Я нашел решение, когда N=1 (то есть при попытке выбрать ровно один элемент случайным образом из огромной последовательности):

import random
items = range(1, 10) # Imagine this is a huge sequence of unknown length
count = 1
selected = None
for item in items:
    if random.random() * count < 1:
        selected = item
    count += 1

Но как я могу добиться того же для других значений N (скажем, N=3)?

Источник

9 ответов

Решение

Используйте отбор проб из пласта. Это очень простой алгоритм, который работает для любого N,

Вот одна реализация Python, а вот другая.

Источник

Если ваша последовательность достаточно коротка, чтобы считывать ее в память и случайным образом сортировать ее, то простым подходом было бы просто использовать random.shuffle:

import random
arr=[1,2,3,4]

# In-place shuffle
random.shuffle(arr)

# Take the first 2 elements of the now randomized array
print arr[0:2]
[1, 3]

В зависимости от типа вашей последовательности, вам может потребоваться преобразовать ее в список, вызвав list(your_sequence) на нем, но это будет работать независимо от типов объектов в вашей последовательности.

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

Источник

Простейший ответ, который я нашел в SO:

import random

my_list = [1, 2, 3, 4, 5]
num_selections = 2

new_list = random.sample(my_list, num_selections)
Источник

Если у вас есть версия Python 3.6+, вы можете использовать выбор

from random import choices

items = range(1, 10)
new_items = choices(items, k = 3)

print(new_items) 
[6, 3, 1]
Источник

Следующее даст вам N случайных элементов из массива X

import random
list(map(lambda _: random.choice(X), range(N)))
Источник

@NPE верна, но реализации, на которые ссылаются, являются неоптимальными и не очень "питоническими". Вот лучшая реализация:

def sample(iterator, k):
    """
    Samples k elements from an iterable object.

    :param iterator: an object that is iterable
    :param k: the number of items to sample
    """
    # fill the reservoir to start
    result = [next(iterator) for _ in range(k)]

    n = k - 1
    for item in iterator:
        n += 1
        s = random.randint(0, n)
        if s < k:
            result[s] = item

    return result

Редактировать Как @panda-34 указал, что оригинальная версия была ошибочной, но не потому, что я использовал randint против randrange, Проблема в том, что мое первоначальное значение для n не учитывать тот факт, что randint включительно на обоих концах диапазона. Принятие этого во внимание устраняет проблему. (Примечание: вы также можете использовать randrange поскольку он включает минимальное значение и исключает максимальное значение.)

Источник

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

Предположим, вы выбрали случайным образом N предметов из K и видите (K + 1) -й предмет. Примите это с вероятностью N / (K + 1) и его вероятности в порядке. Текущие предметы попали с вероятностью N / K и выброшены с вероятностью (N / (K + 1))(1 / N) = 1 / (K + 1), так что выжить с вероятностью (N / K)(K / (K + 1)) = N / (K + 1), поэтому их вероятности тоже в порядке.

И да, я вижу, что кто-то указал вам на отбор проб из пласта - это одно из объяснений того, как это работает.

Источник

В качестве упомянутой выше работы по отбору проб из резервуара. Другой вариант - создать случайное число для каждого числа, которое вы видите, и выбрать верхние k чисел.

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

Источник

Есть одна реализация из numpy библиотека.

При условии, что N меньше длины массива, вам нужно будет сделать следующее:

# my_array is the array to be sampled from
assert N <= len(my_array)
indices = np.random.permutation(N)  # Generates shuffled indices from 0 to N-1
sampled_array = my_array[indices]

Если вам нужно выбрать весь массив, а не только первый N позиции, то вы можете использовать:

import random
sampled_array = my_array[random.sample(len(my_array), N)]
Источник

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

from random import randint

random_nums = []
N = # whatever number of random numbers you want
r = # lower bound of number range
R = # upper bound of number range

x = 0

while x < N:
    random_num = randint(r, R) # inclusive range
    if random_num in random_nums:
        continue
    else:
        random_nums.append(random_num)
        x += 1

Причина цикла while над циклом for заключается в том, что он позволяет упростить реализацию отсутствия пропуска при генерации случайных чисел (т. Е. Если вы получите 3 дубликата, вы не получите N-3 чисел).

Источник
Другие вопросы по тегам