Auswahl von N verschiedenen Elementen nach dem Zufallsprinzip aus einer Sequenz unbekannter Länge, in nur einer Iteration

Question

Ich versuche, einen Algorithmus zu schreiben, der N verschiedene Elemente aus einer Sequenz zufällig auswählen, ohne die Größe der Sequenz im Voraus zu kennen, und wenn es teuer ist, die Sequenz mehr als einmal zu iterieren . Die Elemente der Sequenz könnten zum Beispiel die Zeilen einer großen Datei sein.

Ich habe eine Lösung gefunden, wenn N=1 ist (d.h. "wähle genau ein Element zufällig aus einer großen Folge aus"):

import random
items = range(1, 10) # Imagine this is a huge sequence of unknown length
count = 1
selected = None
for item in items:
    if random.random() * count < 1:
        selected = item
    count += 1

Aber wie kann ich das Gleiche für andere Werte von N (z. B. N=3) erreichen?

Answer 1

Das folgende Beispiel liefert N zufällige Elemente aus einem Array X

import random
list(map(lambda _: random.choice(X), range(N)))

Answer 2

Es sollte ausreichen, jedes neue Element nur einmal zu akzeptieren oder abzulehnen und, wenn Sie es akzeptieren, ein zufällig ausgewähltes altes Element zu verwerfen.

Angenommen, Sie haben N Artikel von K nach dem Zufallsprinzip ausgewählt und sehen einen (K+1)-ten Artikel. Akzeptieren Sie ihn mit der Wahrscheinlichkeit N/(K+1) und seine Wahrscheinlichkeiten sind OK. Die aktuellen Elemente wurden mit der Wahrscheinlichkeit N/K angenommen und werden mit der Wahrscheinlichkeit (N/(K+1)) herausgeworfen. (1/N) = 1/(K+1), überleben also mit einer Wahrscheinlichkeit von (N/K) (K/(K+1)) = N/(K+1), also sind auch ihre Wahrscheinlichkeiten in Ordnung.

Und ja, ich sehe, jemand hat Sie auf das Reservoir Sampling hingewiesen - dies ist eine Erklärung, wie das funktioniert.

Answer 3

Wie aix erwähnte, funktioniert die Entnahme von Wasserproben. Eine andere Möglichkeit ist, für jede Zahl, die Sie sehen, eine Zufallszahl zu generieren und die besten k Zahlen auszuwählen.

Um es iterativ zu tun, halten Sie einen Heap von k (Zufallszahl, Zahl) Paaren und jedes Mal, wenn Sie eine neue Zahl sehen, fügen Sie in den Heap ein, wenn sie größer ist als der kleinste Wert im Heap.

Answer 4

Dies war meine Antwort auf eine doppelte Frage (die geschlossen wurde, bevor ich sie stellen konnte), die etwas damit zu tun hatte ("Generierung von Zufallszahlen ohne Duplikate"). Da es sich um einen anderen Ansatz als die anderen Antworten handelt, lasse ich sie hier stehen, falls sie zusätzliche Erkenntnisse liefert.

from random import randint

random_nums = []
N = # whatever number of random numbers you want
r = # lower bound of number range
R = # upper bound of number range

x = 0

while x < N:
    random_num = randint(r, R) # inclusive range
    if random_num in random_nums:
        continue
    else:
        random_nums.append(random_num)
        x += 1

Der Grund für die while-Schleife gegenüber der for-Schleife ist, dass sie eine einfachere Implementierung von Non-Skipping bei der Zufallsgenerierung ermöglicht (d.h. wenn Sie 3 Duplikate erhalten, werden Sie nicht N-3 Zahlen erhalten).

Answer 5

Es gibt eine Implementierung aus dem numpy Bibliothek.

Unter der Annahme, dass N kleiner ist als die Länge des Arrays, müssen Sie Folgendes tun:

# my_array is the array to be sampled from
assert N <= len(my_array)
indices = np.random.permutation(N)  # Generates shuffled indices from 0 to N-1
sampled_array = my_array[indices]

Wenn Sie das gesamte Array abtasten müssen und nicht nur das erste N Positionen, dann können Sie verwenden:

import random
sampled_array = my_array[random.sample(len(my_array), N)]