Erhalten Sie zufällige Stichprobe aus der Liste, während Sie die Bestellung von Artikeln beibehalten?

Einfach-zu-code-O(N + K*log(K)) Weg

Nehmen Sie eine Stichprobe ohne Ersetzung der Indizes Sortieren der Indizes, und nehmen Sie Sie aus dem original.

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

Oder prägnanter:

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

Optimiert O(N) Zeit, O(1)-Hilfs-Platz Weg

Können Sie alternativ auch eine Mathe-trick und iterativ Durchlaufen myList von Links nach rechts, mit der Auswahl der zahlen mit sich dynamisch verändernden Wahrscheinlichkeit (N-numbersPicked)/(total-numbersVisited). Der Vorteil dieses Ansatzes ist, dass es ein O(N) Algorithmus, da es sich nicht um die Sortierung!

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

Proof-of-concept-und test, die Wahrscheinlichkeiten richtig sind:

Simuliert mit 1 Billion Pseudo-zufälligen Muster, die im Laufe von 5 Stunden:

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

Wahrscheinlichkeiten abweichen von den wahren Wahrscheinlichkeiten weniger ein Faktor 1.0001. Läuft dieser test führte erneut zu einer anderen Reihenfolge, was bedeutet, es ist nicht voreingenommen gegenüber einer Bestellung. Test mit weniger Proben für [0,1,2,3,4], k=3 und [0,1,2,3,4,5], k=4 hatte ähnliche Ergebnisse.

edit: Nicht sicher, warum die Leute abstimmen falsch Kommentare oder Angst zu upvote... NEIN, es ist nichts falsch mit dieser Methode. =)

(Auch ein nützlicher Hinweis von Benutzer tegan in die Kommentare: Wenn Sie diese python2 Sie verwenden möchten, xrange, wie üblich, wenn Sie wirklich über zusätzlichen Platz.)

Bearbeiten: Beweis: betrachtet man die gleichmäßige Verteilung (ohne Ersatz) zur Auswahl einer Teilmenge von k aus einer Bevölkerung seq Größe len(seq) können wir betrachten eine partition an einen beliebigen Punkt i in 'linken' (0,1,...,i-1) und 'rechten' (i,i+1,...,len(seq)). Da holten wir numbersPicked von der linken bekannt Teilmenge, die übrigen müssen aus der gleichen gleichmäßige Verteilung auf die Recht unbekannte Teilmenge, obwohl die Parameter sind jetzt anders. Insbesondere die Wahrscheinlichkeit, dass seq[i] enthält eine gewählte element #remainingToChoose/#remainingToChooseFrom oder (k-numbersPicked)/(len(seq)-i)so simulieren wir, und recurse auf das Ergebnis. (Muss Abbrechen, da wenn #remainingToChoose == #remainingToChooseFrom, dann alle restlichen Wahrscheinlichkeiten sind 1.) Das ist vergleichbar mit einer Wahrscheinlichkeit Baum, die passiert werden dynamisch generiert. Grundsätzlich können Sie simulieren eine gleichmäßige Wahrscheinlichkeitsverteilung, die durch Klimaanlage auf Vorherige Entscheidungen (wie Sie wachsen, die Wahrscheinlichkeit, Baum, Holen Sie die Wahrscheinlichkeit, dass der aktuelle Zweig, so dass es aposteriori der gleiche wie vor verlässt, d.h. Zugriff auf Vorherige Entscheidungen; dies wird funktionieren, weil diese Wahrscheinlichkeit ist einheitlich genau N/k).

Bearbeiten: Timothy Shields erwähnt Reservoir Samplingdas ist die Verallgemeinerung dieser Methode, wenn Sie len(seq) ist unbekannt (wie bei einem generator-Ausdruck). Speziell der eine notiert als "Algorithmus R" ist O(N) und O(1) Speicherplatz, wenn in-place, es bedeutet, dass man die ersten N-element und langsam, Sie zu ersetzen (ein Hinweis auf eine induktive Beweis wird auch gegeben). Es gibt auch nützliche Varianten verteilt und verschiedene Varianten von reservoir-sampling finden Sie auf der wikipedia-Seite.

Bearbeiten: Hier ist ein weiterer Weg, um code unten in eine mehr semantisch naheliegender Weise.

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)

)

InformationsquelleAutor der Antwort ninjagecko

Offenbar random.sample wurde in python 2.3

also für die version, die unter, die wir verwenden können shuffle (Beispiel für 4 items):

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

InformationsquelleAutor der Antwort Yochai Timmer