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

Wenn Ihre Sequenz kurz genug ist, dass das Einlesen in den Speicher und das zufällige Sortieren akzeptabel ist, dann wäre ein einfacher Ansatz die Verwendung von random.shuffle :

import random
arr=[1,2,3,4]

# In-place shuffle
random.shuffle(arr)

# Take the first 2 elements of the now randomized array
print arr[0:2]
[1, 3]

Je nach dem Typ Ihrer Sequenz müssen Sie sie möglicherweise in eine Liste umwandeln, indem Sie list(your_sequence) aber dies funktioniert unabhängig von den Objekttypen in Ihrer Sequenz.

Wenn Sie Ihre Sequenz nicht im Speicher unterbringen können oder die Speicher- oder CPU-Anforderungen dieses Ansatzes für Sie zu hoch sind, müssen Sie natürlich eine andere Lösung verwenden.

Answer 2

Utilice Lagerstättenbeprobung . Es ist ein sehr einfacher Algorithmus, der für jede N .

Hier ist eine Python-Implementierung, und aquí ist eine andere.

Answer 3

Die einfachste Lösung, die ich gefunden habe, ist este Antwort in SO, unten etwas verbessert:

import random

my_list = [1, 2, 3, 4, 5]
how_big = 2

new_list = random.sample(my_list, how_big)

# To preserve the order of the list, you could do:
randIndex = random.sample(range(len(my_list)), how_big)
randIndex.sort()
new_list = [my_list[i] for i in randIndex]

Answer 4

Wenn Sie eine Python-Version von 3.6+ haben, können Sie die Optionen

from random import choices

items = range(1, 10)
new_items = choices(items, k = 3)

print(new_items) 
[6, 3, 1]

Answer 5

@NPE hat recht, aber die Implementierungen, auf die verwiesen wird, sind suboptimal und nicht sehr "pythonisch". Hier ist eine bessere Implementierung:

def sample(iterator, k):
    """
    Samples k elements from an iterable object.

    :param iterator: an object that is iterable
    :param k: the number of items to sample
    """
    # fill the reservoir to start
    result = [next(iterator) for _ in range(k)]

    n = k - 1
    for item in iterator:
        n += 1
        s = random.randint(0, n)
        if s < k:
            result[s] = item

    return result

bearbeiten Wie @panda-34 feststellte, war die ursprüngliche Version fehlerhaft, aber nicht, weil ich mit randint vs randrange . Das Problem ist, dass mein Anfangswert für n nicht die Tatsache berücksichtigt, dass randint ist an beiden Enden des Bereichs enthalten. Wenn man dies berücksichtigt, ist das Problem behoben. (Hinweis: Sie könnten auch randrange da sie den Minimalwert einschließt und den Maximalwert ausschließt).