Algorithmus fuer zufaellige Auswahl gesucht

13/05/2009 - 16:34 von ram | Report spam
Man stelle sich eine Liste von Eintràgen vor (könnten auch mal
»viele« sein, beispielsweise 1E4, 1E5 oder 1E6). Jeder Eintrag
hat eine »Wahrscheinlichkeitszahl«, beispielsweise im Bereich
von 0 bis 10000.

Nun soll aus dieser Liste ein Eintrag ausgewàhlt werden, wobei
die Wahrscheinlichkeit der Auswahl eines bestimmten Eintrags
proportional zu dieser »Wahrscheinlichkeitszahl« sein soll.
(Genauer: Sind A und B zwei Eintràge, soll der Quotient der
Wahrscheinlichkeiten ihrer Auswahl dem Quotienten ihrer
Wahrscheinlichkeitszahlen in guter Nàherung gleich sein.)

Gesucht ist ein Algorithmus für eine prozedurale oder
objektorientiert-prozedurale Sprache (der hier aber auch in
deutscher Sprache formuliert werden kann), der unter
Verwendung eines Pseudozufallszahlengenerators einen Eintrag
aus dieser Liste unter Berücksichtigung der zuvorgenannten
Bedingung auswàhlt.

Ich könnte mir vorstellen, das Intervall aller möglichen
Pseudozufallszahlen in so viel Teilintervalle zu unterteilen,
wie es Eintràge gibt, so daß die Größe eines Teilintervalls
der Wahrscheinlichkeitszahl des ihm entsprechenden Eintrags
proportional ist, und dann zu ermitteln, in welches Intervall
eine Pseudozufallszahl fàllt, was mir aber noch als nicht so
elegant erscheint.

Wenn man das in C mit rand() realisieren will, kann es
außerdem ein Problem sein, wenn RAND_MAX beispielsweise nur
32767 ist, aber die Liste schon mehr als 32767 Eintràge hat.
Dann gibt es ja mehr Möglichkeiten als Zufallszahlen. Aber
auch, wenn die Liste nun nur 10000 Eintràge haben sollte, wàre
die Granularitàt der Intervalle dann schon zu grob für eine
gute Annàherung an die gewünschten Wahrscheinlichkeiten.
 

Lesen sie die antworten

#1 Sebastian Biallas
14/05/2009 - 14:21 | Warnen spam
Stefan Ram wrote:
Man stelle sich eine Liste von Eintràgen vor (könnten auch mal
»viele« sein, beispielsweise 1E4, 1E5 oder 1E6). Jeder Eintrag
hat eine »Wahrscheinlichkeitszahl«, beispielsweise im Bereich
von 0 bis 10000.



0 ist ja schonmal schlecht, wenn es um Quotienten geht.

Nun soll aus dieser Liste ein Eintrag ausgewàhlt werden, wobei
die Wahrscheinlichkeit der Auswahl eines bestimmten Eintrags
proportional zu dieser »Wahrscheinlichkeitszahl« sein soll.
(Genauer: Sind A und B zwei Eintràge, soll der Quotient der
Wahrscheinlichkeiten ihrer Auswahl dem Quotienten ihrer
Wahrscheinlichkeitszahlen in guter Nàherung gleich sein.)



Ohne mehr über den Aufbau der Liste zu wissen (wie sind die
Wahrscheinlichkeiten verteilt?), làsst sich dafür wohl kaum ein
Algorithmus angeben, der sich erstmal die gesamte Liste anschaut.

Gruß,
Sebastian

Ähnliche fragen