Pobrać losową próbkę z listy przy zachowaniu kolejności przedmiotów?

Mam posortowaną listę, powiedzmy: (to nie tylko liczby, to lista obiektów, które są sortowane za pomocą skomplikowanego, czasochłonnego algorytmu)

mylist = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,9  , 10 ]

Czy jest jakaś funkcja Pythona, która poda mi N elementów, ale zachowa kolejność?

Przykład:

randomList = getRandom(mylist,4)
# randomList = [ 3 , 6 ,7 , 9 ]
randomList = getRandom(mylist,4)
# randomList = [ 1 , 2 , 4 , 8 ]

itp...

Poniższy kod wygeneruje losową próbkę o rozmiarze 4:

import random

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

(uwaga: w Pythonie 2 lepiej używać xrangezamiast range)

Wyjaśnienie

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

generuje losową próbkę indeksów z oryginalnej listy.

Indeksy te są następnie sortowane, aby zachować kolejność elementów na oryginalnej liście.

Wreszcie, zrozumienie listy wyciąga rzeczywiste elementy z pierwotnej listy, biorąc pod uwagę wybrane indeksy.

Prosty do kodowania sposób O (N + K * log (K))

Wybierz losową próbkę bez zamiany wskaźników, posortuj wskaźniki i weź je z oryginału.

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

Lub bardziej zwięźle:

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

Zoptymalizowany czas O (N), O (1) - droga pomocnicza

Możesz alternatywnie użyć sztuczki matematycznej i iteracyjnie przechodzić myListod lewej do prawej, wybierając liczby z dynamicznie zmieniającym się prawdopodobieństwem (N-numbersPicked)/(total-numbersVisited). Zaletą tego podejścia jest to, że jest to O(N)algorytm, ponieważ nie obejmuje sortowania!

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

Dowód koncepcji i sprawdzenie, czy prawdopodobieństwa są prawidłowe :

Symulowano 1 bilionem próbek pseudolosowych w ciągu 5 godzin:

>>> 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
})

Prawdopodobieństwa odbiegają od prawdziwych prawdopodobieństw o ​​współczynnik mniejszy niż 1.0001. Uruchomienie tego testu ponownie spowodowało zmianę kolejności, co oznacza, że ​​nie jest ukierunkowany na jedną kolejność. Uruchomienie testu z mniejszą liczbą próbek dla [0,1,2,3,4], k=3i [0,1,2,3,4,5], k=4dało podobne wyniki.

edycja: Nie wiem, dlaczego ludzie głosują za niewłaściwymi komentarzami lub boją się głosować za ... NIE, nie ma nic złego w tej metodzie. =)

(Również przydatna uwaga od użytkownika tegan w komentarzach: jeśli to jest python2, jak zwykle będziesz chciał użyć xrange, jeśli naprawdę zależy ci na dodatkowej przestrzeni.)

edytuj : Dowód: Biorąc pod uwagę równomierny rozkład (bez zamiany) wybierania podzbioru kpopulacji seqo wielkości len(seq), możemy rozważyć podział w dowolnym punkcie ina `` lewy '' (0,1, ..., i-1) i 'right' (i, i + 1, ..., len (seq)). Biorąc pod uwagę, że wybraliśmy numbersPickedz lewego znanego podzbioru, pozostała część musi pochodzić z tego samego jednorodnego rozkładu z prawego nieznanego podzbioru, chociaż parametry są teraz inne. W szczególności prawdopodobieństwo, że seq[i]zawiera wybrany element, wynosi #remainingToChoose/#remainingToChooseFromlub(k-numbersPicked)/(len(seq)-i), więc symulujemy to i powtarzamy wynik. (To musi się skończyć, ponieważ jeśli #remainingToChoose == #remainingToChooseFrom, to wszystkie pozostałe prawdopodobieństwa wynoszą 1.) Jest to podobne do drzewa prawdopodobieństwa, które jest generowane dynamicznie. Zasadniczo możesz zasymulować jednolity rozkład prawdopodobieństwa, uzależniając od wcześniejszych wyborów (powiększając drzewo prawdopodobieństwa, wybierasz prawdopodobieństwo obecnej gałęzi tak, że jest aposteriori takie samo jak poprzednie liście, tj. Uwarunkowane wcześniejszymi wyborami; to zadziała, ponieważ to prawdopodobieństwo jest równomiernie dokładnie N / k).

edycja : Timothy Shields wspomina o próbkowaniu rezerwuaru , które jest uogólnieniem tej metody, gdy len(seq)jest nieznana (na przykład z wyrażeniem generatora). W szczególności ten oznaczony jako „algorytm R” to przestrzeń O (N) i O (1), jeśli jest wykonywany na miejscu; polega na wzięciu pierwszego elementu N i powolnej ich wymianie (podpowiedź o dowodzie indukcyjnym). Istnieją również przydatne, rozproszone warianty i różne warianty pobierania próbek ze zbiorników, które można znaleźć na stronie wikipedii.

edycja : Oto inny sposób zakodowania go poniżej w bardziej semantycznie oczywisty sposób.

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)

)

Może możesz po prostu wygenerować próbkę indeksów, a następnie zebrać pozycje ze swojej listy.

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

Najwyraźniej random.samplezostał wprowadzony w Pythonie 2.3

więc dla wersji pod nią możemy użyć shuffle (przykład dla 4 pozycji):

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

random.sample zaimplementuj to.

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