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

простой в коде O(N + K*log (K)) способ

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

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

или более лаконично:

[x[1] for x in sorted(random.sample(enumerate(myList),K))]

---

оптимизирована о(n) времени, o(1) по-вспомогательный-способом

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

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

доказательство концепции и проверка правильности вероятностей:

смоделировано с 1 триллионом псевдослучайных образцов в течение 5 часов:

>>> Counter(
        tuple(orderedSampleWithoutReplacement([0,1,2,3], 2))
        for _ in range(10**9)
    )
Counter({
    (0, 3): 166680161, 
    (1, 2): 166672608, 
    (0, 2): 166669915, 
    (2, 3): 166667390, 
    (1, 3): 166660630, 
    (0, 1): 166649296
})

вероятности отличаются от истинных вероятностей менее чем в 1,0001 раза. Запуск этого теста снова привел к другому порядку, что означает, что он не смещен в сторону одного порядка. Бегущий тест с меньшим количеством образцов для [0,1,2,3,4], k=3 и [0,1,2,3,4,5], k=4 имели аналогичные результаты.

edit: не знаю, почему люди голосуют за неправильные комментарии или боятся голосовать... Нет, в этом методе нет ничего плохого. =)

(также Полезная заметка от пользователя tegan в комментариях: если это python2, вы захотите использовать xrange, как обычно, если вы действительно заботитесь о дополнительном пространстве.)

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

edit: Тимофей щитов упоминает Отбор Проб Из Резервуара, который является обобщением этого метода, когда len(seq) неизвестно (например, с выражением генератора). В частности, тот, который отмечен как "алгоритм R", является o(N) и O(1) пространством, если он выполняется на месте; он включает в себя первый элемент N и медленно заменяет их (намек на индуктивное доказательство также с учетом.) Есть также полезные распределенные варианты и разные варианты отбора проб из резервуара, которые можно найти на странице Википедии.

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

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)

)

может быть, вы можете просто создать образец индексов, а затем собирать предметы из списка.

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

видимо random.sample был введен в Python 2.3

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

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

случайные.пример реализации этого.

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