Seite 1 von 1
Zufall: Objekt anhand Wahrscheinlichkeit aus Liste wählen
Verfasst: Freitag 13. Januar 2012, 13:16
von microkernel
Hallo!
Ich habe ein Liste von Elementen, welche beispielsweise so gegliedert ist:
Code: Alles auswählen
seq = [("A", 0.25), ("B", 0.25), ("C", 0.2), ("D", 0.4)]
Die Kommazahl in jeder Tulpe gibt die Wahrscheinlichkeit an, ob ein Buchstabe gewählt wird. Nun will ich anhand der jeweiligen Wahrscheinlichkeiten zufällig ein Buchstabe aus dieser Sequenz wählen.
Wie kann ich das machen?
Re: Zufall: Objekt anhand Wahrscheinlichkeit aus Liste wähle
Verfasst: Freitag 13. Januar 2012, 13:36
von Hyperion
Vielleicht hilft Dir
das?
Re: Zufall: Objekt anhand Wahrscheinlichkeit aus Liste wähle
Verfasst: Freitag 13. Januar 2012, 13:41
von yipyip
Re: Zufall: Objekt anhand Wahrscheinlichkeit aus Liste wähle
Verfasst: Freitag 13. Januar 2012, 13:43
von /me
microkernel hat geschrieben:Die Kommazahl in jeder Tulpe gibt die Wahrscheinlichkeit an, ob ein Buchstabe gewählt wird.
"Tulpe" ist gut!
Ich würde das mit
bisect lösen. Zunächst einmal ermittelt man die jeweiligen Grenzen.
Code: Alles auswählen
from __future__ import print_function
from __future__ import unicode_literals
from bisect import bisect
from collections import defaultdict
import random
seq = [("A", 0.25), ("B", 0.25), ("C", 0.2), ("D", 0.4)]
last = 0
breakpoints = []
for value in seq:
breakpoints.append(last + value[1])
last += value[1]
print(breakpoints)
Jetzt würfeln wir im Gesamtwertebereich einfach mal einen Haufen Werte aus und schauen mal, ob die Verteilung einigermaßen passt.
Code: Alles auswählen
d = defaultdict(int)
for count in xrange(11000):
pos = bisect(breakpoints, random.random() * last)
d[seq[pos]] += 1
print(d)
Bei mir sieht das recht gut aus.
Re: Zufall: Objekt anhand Wahrscheinlichkeit aus Liste wähle
Verfasst: Freitag 13. Januar 2012, 16:11
von microkernel
@Hyperion: Jap
Hab folgendes nun eingebaut:
Code: Alles auswählen
import random
def weighted_choice(items):
"""items is a list of tuples in the form (item, weight)"""
assert map(lambda lst: float(lst[1]), items).count(1.0) <= 1
weight_total = sum((item[1] for item in items))
n = random.uniform(0, weight_total)
for item, weight in items:
if n < weight or weight == 1.0:
return item
n -= weight
return item