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

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

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

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

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

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

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

Answer 3

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

Answer 4

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