Gewichtetes Array

Hi!

Ich habe hier variierendes Array mit 0 bis 13 Einträgen aus dem ich sehr häufig ein zufälliges Element rauspicke(AS3 Code):

var matchingGeometrys:Vector.<Geometry>;
   var randomPick:int = Math.floor(Math.random() * matchingGeometrys.length);
   var rndMatchingGeometry:Geometry = matchingGeometrys[randomPick];

Nun wollte ich, dass die hinteren Einträge eine niedrigere Wahrscheinlichkeit haben getroffen zu werden. Wie mache ich das am besten? Ich hab an eine Verteilungsfunktion gedacht, bin aber grad am grübeln wie ich das mit random() vereine und welche Verteilungsfunktion geeignet / anpassbar ist.

Danke!

MfG
Dudeldu

SeppJ

Dudeldu schrieb:

wie ich das mit random() vereine

Verteilungsfunktionen nehmen normalerweise einen (oder mehrere) Werte einer gleichverteilten Zufallsvariablen als Eingabe und geben dann als Ergebnis eine Zufallszahl nach der gewünschten Verteilung zurück. Je nach Sprache/Framework nehmen sie eventuell auch den Zufallsgenerator selbst als Argument, eben damit der Nutzer nicht mit Details konfrontiert wird, wie viele Zufallszahlen intern gezogen werden. Kommt eben ganz drauf an, was du benutzt. Deinen Code kann ich leider nicht eindeutig einer bestimmten Sprache zuordnen.

und welche Verteilungsfunktion geeignet / anpassbar ist.

Das müsstest du eigentlich selber wissen, denn schließlich kommt dies ganz darauf an, was du erreichen möchtest.

Falls du ohne genaue Pläne einfach nur etwas suchst, was gegen für kleine Werte eine höhere Wahrscheinlichkeit hat als bei großen, dann kämen von den "üblichen" Verteilungsfunktionen folgende in Frage (Verteilungen bitte selber bei Wikipedia nachschlagen):
Geometrische Verteilung (diskret)
Poisson-Verteilung mit λ=1 (diskret)
Exponentialverteilung (kontinuierlich)
Gamma-Verteilung mit k <= 1 (kontinuierlich)
Weibull-Verteilung mit passenden Parametern (kontinuierlich)
Chi-Quadrat-Verteilung mit passenden Parametern (kontinuierlich)
F-Verteilung mit passenden Parametern (kontinuierlich)
und bestimmt noch viele mehr, besonders wenn man noch mögliche Folgetransformationen in Betracht zieht.

Weiterhin kannst du viele einfach Funktionen direkt selber zu einer Verteilungsfunktion umformen:
https://en.wikipedia.org/wiki/Inverse_transform_sampling
Es ist sehr gut möglich, dass du mit dieser Methode am ehesten dein Ziel erreichst. Die obigen Verteilungsfunktionen sind in ihrer Form motiviert dadurch, gewisse mathematische Zusammenhänge auszudrücken. Größtmögliche Einfachheit spielte da keine spezielle Rolle.

Oder wenn das nicht praktikabel ist, kann man mit ausreichender Gewaltanwendung jede denkbare^* Verteilungsfunktion nachbilden:
https://en.wikipedia.org/wiki/Rejection_sampling

^*: Zumindest so lange wir nicht zu kreativ werden. Wir sollten schon noch im Rⁿ bleiben.

Die meisten Verteilungsfunktionen von SeppJ sind für ein Array Overkill.

Du weist jedem Element k eine Gewichtung (Wahrscheinlichkeit) f(k) zu.
Dann berechnest du die Präfixsummen f(1),f(1)+f(2),...,f(1)+...+f(n) vor.
Bestimme dann eine uniform verteilte zufällige reelle Zahl x zwischen 0 und f(1)+...+f(n).
Das Element ist dann das mit dem Index k, für den f(1)+...+f(k)>=x aber f(1)+...+f(k)+f(k+1)<x. Das kannst du mit binärer Suche machen, die Laufzeit wäre dann log(n).