Получить случайную выборку из списка, сохраняя порядок элементов?

Следующий код сгенерирует случайную выборку размера 4:

import random

sample_size = 4
sorted_sample = [
    mylist[i] for i in sorted(random.sample(range(len(mylist)), sample_size))
]

(примечание: в Python 2 лучше использовать xrange вместо range)

Пояснение

random.sample(range(len(mylist)), sample_size)

генерирует случайную выборку индексов исходного списка.

Затем эти индексы сортируются, чтобы сохранить порядок элементов в исходном списке.

Наконец, понимание списка извлекает фактические элементы из исходного списка с учетом выбранных индексов.

Простой в коде способ O(#picks*log(#picks))

Возьмите случайную выборку без замены индексов, отсортируйте индексы и возьмите их из оригинала.

indices = random.sample(range(len(myList)), K)
[myList[i] for i in sorted(indices)]

random.sample(seq, K) будет случайным образом и одновременно выбирать K элементов из совокупности в seq без замены. Когда мы делаем это с range, это O (1) на выборку, поскольку объект range в python является разреженным и фактически не создает полный список (в частности, реализация cpython вызывает len(seq) и более поздние seq[i] для объекта диапазона, которые виртуализированы /faked и, следовательно, O (1)). Затем вы просматриваете случайные индексы (по порядку).

Если у вас есть итератор (например, выражение генератора), вы можете сначала преобразовать его в список, а затем выполнить приведенный выше ответ. Если ваш итератор имеет неограниченную длину, вы можете использовать технику из следующего раздела, которая гораздо менее эффективна, но может быть интересна с интеллектуальной точки зрения (например, если вы работаете с небольшими ограниченными списками в функциональном языке, который еще не поддерживает индексацию). , или гигантские потоки, которые превышают размер ОЗУ и диска):

(Также полезное примечание от пользователя tegan в комментариях: если это python2, вы, как обычно, захотите использовать xrange. В противном случае у вас будет алгоритм O(N), а не O(#picks).

Медленный/потоковый O(arrayLen)-время, O(1)-вспомогательный-пространственный способ для неиндексируемых последовательностей

В качестве альтернативы вы можете использовать математический трюк и итеративно проходить myList слева направо, выбирая числа с динамически изменяющейся вероятностью (N-numbersPicked)/(total-numbersVisited). Этот подход O(N), так как он посещает все один раз (быстрее, чем сортировка, которая составляет O(N log(N)), хотя и намного медленнее, чем прямая индексация K выборок, как мы делали в предыдущем разделе (что было O(K log(K)). ) после сортировки).

from __future__ import division

def orderedSampleWithoutReplacement(seq, k):
    if not 0<=k<=len(seq):
        raise ValueError('Required that 0 <= sample_size <= population_size')

    numbersPicked = 0
    for i,number in enumerate(seq):
        prob = (k-numbersPicked)/(len(seq)-i)
        if random.random() < prob:
            yield number
            numbersPicked += 1

Доказательство: учитывая равномерное распределение (без замены) выбора подмножества k из совокупности seq размера len(seq), мы можем рассмотреть разбиение в произвольной точке i на «левые» (0,1,...,i- 1) и «право» (i,i+1,...,len(seq)). Учитывая, что мы выбрали numbersPicked из левого известного подмножества, остальные должны происходить из того же равномерного распределения в правом неизвестном подмножестве, хотя параметры теперь другие. В частности, вероятность того, что seq[i] содержит выбранный элемент, равна #remainingToChoose/#remainingToChooseFrom или (k-numbersPicked)/(len(seq)-i), поэтому мы моделируем это и рекурсивно используем результат. (Это должно прекратиться, поскольку если #remainingToChoose == #remainingToChooseFrom, то все оставшиеся вероятности равны 1.) Это похоже на дерево вероятностей, которое генерируется динамически. По сути, вы можете смоделировать равномерное распределение вероятностей, обуславливая предыдущие варианты выбора (по мере роста дерева вероятностей вы выбираете вероятность текущей ветви таким образом, чтобы она была апостериорно такой же, как и предыдущие листья, т. эта вероятность равно ровно N/k).

(Можно просмотреть историю редактирования этого поста, чтобы найти подробное «доказательство» симуляции, которое ранее было необходимо из-за некоторых отрицательных голосов.)

Вот еще один способ закодировать его ниже, с более семантически названными переменными.

from __future__ import division
import random

def orderedSampleWithoutReplacement(seq, sampleSize):
    totalElems = len(seq)
    if not 0<=sampleSize<=totalElems:
        raise ValueError('Required that 0 <= sample_size <= population_size')
    
    picksRemaining = sampleSize
    for elemsSeen,element in enumerate(seq):
        elemsRemaining = totalElems - elemsSeen
        prob = picksRemaining/elemsRemaining
        if random.random() < prob:
            yield element
            picksRemaining -= 1

from collections import Counter         
Counter(
    tuple(orderedSampleWithoutReplacement([0,1,2,3], 2))
    for _ in range(10**5)
)

редактировать: Тимоти Шилдс упоминает отбор проб резервуара, что-то вроде этот метод (но начинается с выбора кандидатов и случайным образом меняет их местами) и полезен, когда len(seq) неизвестен (например, с выражением генератора). В частности, тот, который отмечен как алгоритм R, имеет вспомогательное пространство O (N) и O (1), если выполняется на месте; он включает в себя взятие первых K элементов и их медленную замену (также дается намек на индуктивное доказательство). Полезные варианты отбора проб из резервуара также можно найти на странице в Википедии. Идея состоит в том, что вы заранее заполняете список возможных возвращаемых значений (которые, как мы предполагаем, помещаются в ОЗУ или на диске), и вероятностно заменяете их по мере повторения списка (который может быть произвольно больше, чем ваша ОЗУ или диск).

Оптимальный способ O(#picks * (1+log(N/#picks))-time, O(1)-aux-space для индексируемых последовательностей

Один примечательный алгоритм описан в статье Reservoir Sampling (ctrl-F Алгоритм L, раздел). оптимальный алгоритм): это оптимальный алгоритм конкурентного фактора, который (как и исходное решение) O (k) по количеству выборок, а не O (n) по количеству элементов списка.

Интуиция здесь такова, что мы можем пропускать произвольные разделы списка, даже не посещая их, потому что количество элементов между выборками не зависит от данных, которые мы видим в списке.

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

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

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

randIndex = random.sample(range(len(mylist)), sample_size)
randIndex.sort()
rand = [mylist[i] for i in randIndex]

По-видимому, random.sample был представлен в python 2.3.

поэтому для версии ниже мы можем использовать перемешивание (пример для 4 элементов):

myRange =  range(0,len(mylist)) 
shuffle(myRange)
coupons = [ bestCoupons[i] for i in sorted(myRange[:4]) ]

random.sample реализует это.

>>> random.sample([1, 2, 3, 4, 5],  3)   # Three samples without replacement
[4, 1, 5]