Was ist die pythischste Art, ein zufälliges Element aus einer Liste zu entfernen?

Question

Angenommen, ich habe eine Liste x mit unbekannter Länge, aus der ich nach dem Zufallsprinzip ein Element einfügen möchte, so dass die Liste das Element danach nicht enthält. Was ist der pythischste Weg, dies zu tun?

Ich kann es eine ziemlich unhandliche combincation von pop verwenden, random.randint und len und mag Lösungen kürzer oder schöner sehen:

import random 
x = [1,2,3,4,5,6] 
x.pop(random.randint(0,len(x)-1)) 

Edit: Was ich versuche zu erreichen ist konsekutiv Pop zufällige Elemente aus einer Liste. (Dh zufällig ein Element Pop und es zu einem Wörterbuch bewegen, zufällig ein anderes Element Pop und in ein anderes Wörterbuch bewegen, ...)

---

Bitte beachte, dass ich verwende Python 2.6 und können keine Lösungen über die Suchfunktion.

Answer 1

Was Sie scheinen bis zu sein, nicht sehr Pythonic in erster Linie sieht. Sie sollten Objekte nicht aus der Mitte einer Liste entfernen, da Listen in allen bekannten Python-Implementierungen als Arrays implementiert sind. Dies ist also eine O(n)-Operation. Wenn Sie diese Funktionalität wirklich als Teil eines Algorithmus benötigen, sollten Sie eine Datenstruktur wie blist auschecken, die effizientes Löschen von der Mitte unterstützt.

In reinen Python, was Sie tun können, wenn Sie Zugang brauchen nicht zu den übrigen Elementen ist nur die Liste mischen und dann über sie iterieren:

lst = [1,2,3] 
random.shuffle(lst) 
for x in lst: 
    # ... 

Wenn Sie wirklich brauchen der Rest (das ist ein bisschen ein Codegeruch, IMHO), zumindest können Sie pop() vom Ende der Liste jetzt (was schnell ist!):

while lst: 
    x = lst.pop() 
    # do something with the element  

In der Regel können Sie oft Ihre Programme ausdrücken mehr elegant wenn Sie mehr verwenden funktionaler Stil, anstatt muting Zustand (wie Sie mit der Liste tun).

Answer 2

Sie werden nicht viel besser als das, aber hier ist eine leichte Verbesserung:

x.pop(random.randrange(len(x))) 

Dokumentation auf random.randrange():

random.randrange ([Start], stoppen [, Schritt ])
Gibt ein zufällig ausgewähltes Element aus range(start, stop, step) zurück. Dies entspricht choice(range(start, stop, step)), erstellt jedoch kein Bereichsobjekt.

Answer 3

Eine Möglichkeit, es zu tun ist:

x.remove(random.choice(x)) 

Answer 4

Hier ist eine andere Alternative: Warum mischen Sie nicht die Liste zuerst, und starten Sie dann Elemente davon zu knallen, bis keine Elemente mehr übrig bleiben?dies wie:

import random 

x = [1,2,3,4,5,6] 
random.shuffle(x) 

while x: 
    p = x.pop() 
    # do your stuff with p 

Answer 5

Um ein einzelnes Element zufällig Index aus einer Liste, wenn die Reihenfolge der übrigen Listenelemente spielt keine Rolle zu entfernen:

import random 

L = [1,2,3,4,5,6] 
i = random.randrange(len(L)) # get random index 
L[i], L[-1] = L[-1], L[i] # swap with the last element 
x = L.pop()     # pop last element O(1) 

Der Swap verwendet wird, zu vermeiden, O (n) Verhalten beim Löschen von einer Mitte einer Liste.

Answer 6

Während ich nicht aus der Liste platzt, bin ich auf diese Frage bei Google gestoßen, als ich versuchte, X zufällige Einträge aus einer Liste ohne Duplikate zu erhalten. Hier ist, was ich schließlich verwendet:

items = [1, 2, 3, 4, 5] 
items_needed = 2 
from random import shuffle 
shuffle(items) 
for item in items[:items_needed]: 
    print(item) 

Diese etwas ineffizient sein kann, wenn Sie eine ganze Liste ist schlurfende aber nur einen kleinen Teil davon, aber ich bin kein Experte Optimierung, also könnte ich falsch sein.

Answer 7

Diese Antwort kommt mit freundlicher Genehmigung von @niklas-b:

"Sie wollen wahrscheinlich etwas wie pypi.python.org/pypi/blist verwenden"

die PYPI page zu zitieren:

... eine Liste artiger Typ mit besserer asymptotischer Leistung und ähnlichem Leistung auf kleinen Listen

Die Blist ist ein Drop-In-Ersatz für die Python-Liste, der bessere Leistung bietet, wenn große Listen geändert werden. Das Blist-Paket bietet auch Sortedlist, Sortedset, Weaksortedlist, Weaksortedset, Sorteddict und Btuple-Typen.

Man würde annehmen, Leistung auf dem Random Access/random Laufenden abgesenkt, da es ein "Copy on Write" Datenstruktur ist. Dies verstößt gegen viele Anwendungsfallannahmen auf Python-Listen, , also verwenden Sie es vorsichtig.

ABER, wenn Ihr Hauptanwendungsfall ist, etwas Seltsames und Unnatürliches mit einer Liste zu tun (wie in dem erzwungenen Beispiel von @OP oder meinem Python 2.6 FIFO Queue-mit-Pass-Over-Problem), dann wird dies passen Sie die Rechnung gut an.

Answer 8

Ich weiß, dass dies eine alte Frage, aber nur für die Dokumentation willen:

Wenn Sie (die Person, die gleiche Frage googeln) tun, was ich denke, Sie tun, was k Anzahl der Elemente ist die Auswahl zufällig aus eine Liste (wo k < = len (yourlist)), aber sicherstellen, dass jedes Element nie mehr als einmal ausgewählt wird (= Sampling ohne Ersatz), könnten Sie random.sample wie @ jf-sebastian schlägt. Aber ohne mehr über den Anwendungsfall zu wissen, weiß ich nicht, ob Sie das brauchen.