Zufall: Objekt anhand Wahrscheinlichkeit aus Liste wählen

[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?

[Hyperion]

Vielleicht hilft Dir das?

[yipyip]

Oder das hier:
http://eli.thegreenplace.net/2010/01/22 ... in-python/

[/me]

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.

[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