случайные предметы из списка

Question

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

Спасибо

Answer 1

Я думаю, ответ на мой вопрос заключается в следующем:

pick first k elements and store them into an array of length k 
for each element x > k 
    insert x with probability k/x 
    choose position at random between 1 and k 

Answer 2

Easy (если к < = п). Это похоже на получение списка k номеров < n. Это будет список позиций чисел, которые нужно получить. Создайте список диапазонов (0..n), получите от него случайные числа k. Вам не нужно будет читать фактический список предметов до последнего момента. Очевидно, что это полезно только тогда, когда конечный список элементов медленно читается (он читается с диска или что-то в этом роде).

Чтобы получить позиции пунктов, чтобы выбрать только сделать:

import random 
itemstopick = random.Random().sample(range(0,n), k) 

Если п, число элементов неизвестно, то вы обязательно начала, выбирая первые к элементам (то есть решение, если к = n). Тогда единственный выбор yu - продолжить чтение элементов и либо выбрать, чтобы новый элемент только что прочитал (и удалить другой элемент), либо сохранить текущие элементы такими, какие они есть. Чтобы придерживаться равномерной вероятности, вам придется уменьшить вероятность выбрать последний прочитанный элемент по мере продолжения. Вероятность сохранения последнего элемента всегда должна быть P (k/n0), когда n0 является значением n в это время. Я не верю, что вы можете сделать лучше.

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

Answer 3

Это зависит от того, есть ли у вас генерируемые случайные значения или нет, если это возможно, если нет, вам придется их генерировать, и вам понадобится примерно от 2 * k до 3 * k операций в что дело

Answer 4

1. Пропуск случайного количества элементов из текущей позиции в списке
2. Возьмите текущий элемент.
3. Если вы достигли конца списка, перейдите к началу списка и перейдите к шагу 1
4. Повторите эти шаги k раз.